<!DOCTYPE html>
<html lang="en">

<!-- Head tag -->
<head>
    <meta charset="utf-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="google-site-verification" content="xBT4GhYoi5qRD5tr338pgPM5OWHHIDR6mNg1a3euekI" />
    <meta name="viewport" content="width=device-width, initial-scale=1">
    <meta name="description" content="">
    <meta name="keyword"  content="">
    <link rel="shortcut icon" href="/img/logo.png">
    <!-- Place this tag in your head or just before your close body tag. -->
    <script async defer src="https://buttons.github.io/buttons.js"></script>
    <title>
        
          集合框架理解 - 宋正兵的博客 | zbsong Blog
        
    </title>

    <link rel="canonical" href="zbsong.top/article/jdk学习之路—集合框架/">

    <!-- Bootstrap Core CSS -->
    <link rel="stylesheet" href="/css/bootstrap.min.css">

    <!-- Custom CSS --> 
    <link rel="stylesheet" href="/css/beantech.min.css">

    <link rel="stylesheet" href="/css/donate.css">
    
    <!-- Pygments Highlight CSS -->
    <link rel="stylesheet" href="/css/highlight.css">

    <link rel="stylesheet" href="/css/widget.css">

    <link rel="stylesheet" href="/css/rocket.css">

    <link rel="stylesheet" href="/css/signature.css">

    <link rel="stylesheet" href="/css/toc.css">

    <!-- Custom Fonts -->
    <!-- <link href="https://maxcdn.bootstrapcdn.com/font-awesome/4.3.0/css/font-awesome.min.css" rel="stylesheet" type="text/css"> -->
    <!-- Hux change font-awesome CDN to qiniu -->
    <link href="https://cdn.staticfile.org/font-awesome/4.5.0/css/font-awesome.min.css" rel="stylesheet" type="text/css">


    <!-- Hux Delete, sad but pending in China
    <link href='http://fonts.googleapis.com/css?family=Lora:400,700,400italic,700italic' rel='stylesheet' type='text/css'>
    <link href='http://fonts.googleapis.com/css?family=Open+Sans:300italic,400italic,600italic,700italic,800italic,400,300,600,700,800' rel='stylesheet' type='text/
    css'>
    -->


    <!-- HTML5 Shim and Respond.js IE8 support of HTML5 elements and media queries -->
    <!-- WARNING: Respond.js doesn't work if you view the page via file:// -->
    <!--[if lt IE 9]>
        <script src="https://oss.maxcdn.com/libs/html5shiv/3.7.0/html5shiv.js"></script>
        <script src="https://oss.maxcdn.com/libs/respond.js/1.4.2/respond.min.js"></script>
    <![endif]-->

    <!-- ga & ba script hoook -->
    <script></script>
</head>


<!-- hack iOS CSS :active style -->
<body ontouchstart="">
	<!-- Modified by Yu-Hsuan Yen -->
<!-- Post Header -->
<style type="text/css">
    header.intro-header{
        
            background-image: url('https://api.dujin.org/bing/1920.php')
            /*post*/
        
    }
    
</style>

<header class="intro-header" >
    <!-- Signature -->
    <div id="signature">
        <div class="container">
            <div class="row">
                <div class="col-lg-8 col-lg-offset-2 col-md-10 col-md-offset-1">
                
                    <div class="post-heading">
                        <div class="tags">
                            
                              <a class="tag" href="/tags/#jdk学习之路" title="jdk学习之路">jdk学习之路</a>
                            
                        </div>
                        <h1>集合框架理解</h1>
                        <!-- <h2 class="subheading">一个集合源码解析系列的阅读笔记</h2> -->
                        <span class="meta">
                            宋正兵 on
                            2021-01-08
                        </span>
                    </div>
                


                </div>
            </div>
        </div>
    </div>
</header>

    <!-- Navigation -->
<nav class="navbar navbar-default navbar-custom navbar-fixed-top">
    <div class="container-fluid">
        <!-- Brand and toggle get grouped for better mobile display -->
        <div class="navbar-header page-scroll">
            <button type="button" class="navbar-toggle">
                <span class="sr-only">Toggle navigation</span>
                <span class="icon-bar"></span>
                <span class="icon-bar"></span>
                <span class="icon-bar"></span>
            </button>
            <a class="navbar-brand" href="/">songzblink</a>
        </div>

        <!-- Collect the nav links, forms, and other content for toggling -->
        <!-- Known Issue, found by Hux:
            <nav>'s height woule be hold on by its content.
            so, when navbar scale out, the <nav> will cover tags.
            also mask any touch event of tags, unfortunately.
        -->
        <div id="huxblog_navbar">
            <div class="navbar-collapse">
                <ul class="nav navbar-nav navbar-right">
                    <li>
                        <a href="/">主页</a>
                    </li>
					<li>
                        <a href="/archive/">归档</a>
                    </li>
					<li>
                        <a href="/tags/">标签</a>
                    </li>
					<li>
                        <a href="/about/">关于</a>
                    </li>
					<!--
					修改about在前面的问题
                    
                        
                    
                        
                        <li>
                            <a href="/about/">关于</a>
                        </li>
                        
                    
                        
                        <li>
                            <a href="/archive/">归档</a>
                        </li>
                        
                    
                        
                        <li>
                            <a href="/tags/">标签</a>
                        </li>
                        
                    
                    -->
                </ul>
            </div>
        </div>
        <!-- /.navbar-collapse -->
    </div>
    <!-- /.container -->
</nav>
<script>
    // Drop Bootstarp low-performance Navbar
    // Use customize navbar with high-quality material design animation
    // in high-perf jank-free CSS3 implementation
    var $body   = document.body;
	// querySelector 获取文档中 id="demo" 的元素
    var $toggle = document.querySelector('.navbar-toggle');
    var $navbar = document.querySelector('#huxblog_navbar');
    var $collapse = document.querySelector('.navbar-collapse');

    $toggle.addEventListener('click', handleMagic)
    function handleMagic(e){
        if ($navbar.className.indexOf('in') > 0) {
        // CLOSE
            $navbar.className = " ";
            // wait until animation end.
            setTimeout(function(){
                // prevent frequently toggle
                if($navbar.className.indexOf('in') < 0) {
                    $collapse.style.height = "0px"
                }
            },400)
        }else{
        // OPEN
            $collapse.style.height = "auto"
            $navbar.className += " in";
        }
    }
</script>


    <!-- Main Content -->
    <!-- Modify by Yu-Hsuan Yen -->

<!-- Post Content -->
<article>
    <div class="container">
        <div class="row">

            <!-- Post Container -->
            <div class="
                col-lg-8 col-lg-offset-2
                col-md-10 col-md-offset-1
                post-container">

				
                <p>阅读博客<a href="https://blog.csdn.net/u011240877/category_6447444.html" target="_blank" rel="noopener">Java 集合框架原理分析</a>的笔记记录，挑了一些觉得重要的内容。</p>
<p>Java 提供的集合都在 java.utils 包下，它们的关系如下面这张类图所示：<img src="https://pic.tyzhang.top/images/2020/12/30/image.png" alt="image.png"></p>
<h1 id="iterator迭代器">Iterator迭代器</h1>
<p>Iterator 是一个集合上的迭代器，用于对集合进行遍历、迭代。它因为有更短的方法名字，允许调用者在遍历过程中语法正确地删除元素而替代掉了 Enumeration 类。</p>
<p>注意这里的 【语法正确】，事实上在使用 Iterator 对容器进行迭代的时候，如果修改容器可能会报 <em>ConcurrentModificationException</em> 的错误。官方称这种情况下的迭代器是 fail-fast 迭代器。</p>
<blockquote>
<p>fail-fast：<em>fail-fast</em> 机制是java集合(Collection)中的一种错误机制。当多个线程对同一个集合的内容进行操作时，就可能会产生<em>fail-fast</em>事件。</p>
</blockquote>
<h2 id="concurrentmodificationexception-出现的原因fail-fast">ConcurrentModificationException 出现的原因（fail-fast）</h2>
<p>以 ArrayList 为例，在调用迭代器的 remove 方法时，程序抛出 ConcurrentModificationException 异常，也就是成为了 fail-fast：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">main</span><span class="params">(String[] args)</span> </span>&#123;</span><br><span class="line">    ArrayList&lt;String&gt; list=<span class="keyword">new</span> ArrayList&lt;String&gt;();</span><br><span class="line">    list.add(<span class="string">"111"</span>);</span><br><span class="line">    list.add(<span class="string">"222"</span>);</span><br><span class="line">    list.add(<span class="string">"333"</span>);</span><br><span class="line"> </span><br><span class="line">    <span class="keyword">for</span>(Iterator&lt;String&gt; iterator=list.iterator();iterator.hasNext();)&#123;</span><br><span class="line">        String ele=iterator.next();</span><br><span class="line">        <span class="keyword">if</span>(ele.equals(<span class="string">"111"</span>)) </span><br><span class="line">            list.remove(<span class="string">"222"</span>);  <span class="comment">// 抛出 ConcurrentModificationException 异常</span></span><br><span class="line">    &#125;</span><br><span class="line">    System.out.println(list);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>可以看到在调用迭代器遍历时，如果使用 Collection 的 remove 方法删除会造成 ConcurrentModificationException 异常。具体可以阅读这篇<a href="https://blog.csdn.net/Jiangshan11/article/details/83038857" target="_blank" rel="noopener">文章</a>。</p>
<p>如何解决呢？单线程的时候删除元素的时候使用迭代器的 remove 方法就可以实现正常的删除了，多线程的时候使用并发集合类。</p>
<h2 id="api">API</h2>
<table>
<thead>
<tr>
<th>方法</th>
<th>用途</th>
</tr>
</thead>
<tbody>
<tr>
<td>boolean hasNext()</td>
<td>如果此列表迭代器在向前遍历列表时有更多元素，则返回true</td>
</tr>
<tr>
<td>E next()</td>
<td>返回列表中的下一个元素并前进光标位置</td>
</tr>
<tr>
<td>void remove()</td>
<td>从列表中删除next()返回的最新元素</td>
</tr>
</tbody>
</table>
<h1 id="listiterator双向迭代器">ListIterator双向迭代器</h1>
<p>ListIterator 的功能：</p>
<ul>
<li>允许我们向前、向后两个方向遍历 List；</li>
<li>可以在遍历时修改 List 的元素；</li>
<li>遍历时获取迭代器当前游标所在的位置。</li>
</ul>
<blockquote>
<p>迭代器没有当前所在元素一说，它只有一个游标（cursor）的概念，游标总是在元素之间。即长度为 N 的集合会有 N+1 个游标的位置。</p>
</blockquote>
<p><img src="https://pic.tyzhang.top/images/2020/12/22/image.png" alt="image.png"></p>
<h2 id="listiterator的获取">ListIterator的获取</h2>
<table>
<thead>
<tr>
<th>方法</th>
<th>用途</th>
</tr>
</thead>
<tbody>
<tr>
<td>ListIterator<e> listIterator()</e></td>
<td>返回此 list 中的 ListIterator 迭代器</td>
</tr>
<tr>
<td>ListIterator<e> listIterator(int index)</e></td>
<td>返回此 list 中的 ListIterator 迭代器，起始位置为 index</td>
</tr>
</tbody>
</table>
<h2 id="api">API</h2>
<p>ListIterator 继承自Iterator 接口，在 Iterator 的基础上增加了 6 个方法：</p>
<table>
<thead>
<tr>
<th>方法</th>
<th>用途</th>
</tr>
</thead>
<tbody>
<tr>
<td>boolean hasPrevious()</td>
<td>判断游标前面是否有元素</td>
</tr>
<tr>
<td>E previois()</td>
<td>返回游标前面的元素，同时游标前移一位。游标前没有元素就报 java.util.NoSuchElementException 的错，所以使用前最好判断一下</td>
</tr>
<tr>
<td>int nextIndex()</td>
<td>返回游标后边元素的索引位置，初始为 0 ；遍历 N 个元素结束时为 N</td>
</tr>
<tr>
<td>void add()</td>
<td>返回列表中的上一个元素并向后移动光标位置</td>
</tr>
<tr>
<td>void set()</td>
<td>从列表中删除next()或previous()返回的最新元素；注意，当没有迭代，也就是没有调用 next() 或者 previous() 直接调用 set 时会报 java.lang.IllegalStateException 错</td>
</tr>
<tr>
<td>void remove()</td>
<td>删除迭代器最后一次操作的元素，注意事项和 set 一样。</td>
</tr>
</tbody>
</table>
<h1 id="collection集合">Collection集合</h1>
<h2 id="集合的概念">集合的概念</h2>
<p>集合，或者叫做容器，是一个包含多个元素的对象。</p>
<p>集合可以对数据进行存储，检索，操作。</p>
<h2 id="集合框架">集合框架</h2>
<p>集合框架是一个代表、操作集合的统一架构。所有的集合框架都包含一下几点：</p>
<ul>
<li><strong>接口</strong>：表示集合的抽象数据类型。接口允许我们操作集合时不必关注具体实现，从而达到“多态”。在面向对象变成语言中，接口通常用来形成规范。</li>
<li><strong>实现类</strong>：集合接口的具体实现，是重用性很高的数据结构。</li>
<li><strong>算法</strong>：用来根据需要对实体类中的对象进行计算，比如查找、排序。</li>
</ul>
<h2 id="java集合框架主要结构图">Java集合框架主要结构图</h2>
<p><img src="https://pic.tyzhang.top/images/2020/12/30/image.png" alt="image.png"></p>
<p>Java 的集合主要分为 Collection 和 Map 两类。</p>
<h2 id="15个核心api">15个核心API</h2>
<table>
<thead>
<tr>
<th>方法</th>
<th>用途</th>
</tr>
</thead>
<tbody>
<tr>
<td>int size()</td>
<td>获取元素个数</td>
</tr>
<tr>
<td>boolean isEmpty()</td>
<td>是否个数为 0</td>
</tr>
<tr>
<td>boolean contains(Object e)</td>
<td>是否包含指定元素</td>
</tr>
<tr>
<td>boolean add(E e)</td>
<td>添加元素，成功时返回 true</td>
</tr>
<tr>
<td>boolean remove(Object e)</td>
<td>删除元素，成功时返回 true</td>
</tr>
<tr>
<td>Iterator<e> iterator()</e></td>
<td>获取迭代器</td>
</tr>
<tr>
<td>boolean containsAll(Collection&lt;?&gt; c)</td>
<td>是否包含指定集合 c 的全部元素</td>
</tr>
<tr>
<td>boolean addAll(Collection&lt;? extends E&gt; c)</td>
<td>添加集合 c 中的所有元素到本集合中，如果集合有改变就返回 true</td>
</tr>
<tr>
<td>boolean removeAll(Collection&lt;?&gt; c)</td>
<td>删除本集合中和集合 c 中一致的元素，如果集合有改变就返回 true</td>
</tr>
<tr>
<td>boolean retainAll(Collection&lt;?&gt; c)</td>
<td>保留本集合和集合 c 中共有的元素，如果集合有改变就返回 true</td>
</tr>
<tr>
<td>void clear()</td>
<td>删除所有元素</td>
</tr>
<tr>
<td>Object[] toArray()</td>
<td>返回一个包含集合中所有元素的数组</td>
</tr>
<tr>
<td><t> T[] toArray(T[] a)</t></td>
<td>返回一个包含集合中所有元素的数组，运行时根据集合元素的类型指定数组的类型</td>
</tr>
</tbody>
</table>
<p>JDK 8 以后，Collection 接口还提供了从集合获取连续流或者并行流：</p>
<ul>
<li><code>Stream&lt;E&gt; stream()</code></li>
<li><code>Stream&lt;E&gt; parallelStream()</code></li>
</ul>
<p>点击这里了解流【待补充】</p>
<h2 id="遍历collection的方法">遍历Collection的方法</h2>
<h3 id="1-for-each语法">1、for-each语法</h3>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">Collection&lt;Person&gt; persons = <span class="keyword">new</span> ArrayList&lt;Person&gt;();</span><br><span class="line"><span class="keyword">for</span> (Person person : persons) &#123; </span><br><span class="line">    System.out.println(person.name);  </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="2-iterator迭代器">2、Iterator迭代器</h3>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">Collection&lt;Person&gt; persons = <span class="keyword">new</span> ArrayList&lt;Person&gt;();</span><br><span class="line">Iterator iterator = persons.iterator();</span><br><span class="line"><span class="keyword">while</span> (iterator.hasNext()) &#123; </span><br><span class="line">    System.out.println(iterator.next());  </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h1 id="listltegt接口">List&lt;E&gt;接口</h1>
<p>List  是一个在元素有序的（保存的顺序就是存储的顺序），可以重复的，可以为 null 的集合（有时也称为“序列”）。</p>
<p>Java 集合框架中最常用的几种 List 实现类是 ArrayList、LinkedList 和 Vector。在各种 List 中，最好的做法是以 ArrayList 作为默认选择。当插入、删除频繁时，使用 LinkedList。Vector 总是比 ArrayList 慢，所以要尽量避免使用它。</p>
<h2 id="list接口扩展的方法">List接口扩展的方法</h2>
<table>
<thead>
<tr>
<th>方法</th>
<th>用途</th>
</tr>
</thead>
<tbody>
<tr>
<td>E get(int index)</td>
<td>获取指定索引上的数据</td>
</tr>
<tr>
<td>E set(int index, E element)</td>
<td>修改指定索引数据</td>
</tr>
<tr>
<td>ListIterator<e> listIterator()</e></td>
<td>返回 ListIterator 接口对象</td>
</tr>
<tr>
<td>static <e> List<e> of(E …e)</e></e></td>
<td>返回包含 n 个元素的不可修改列表，n 不超过10</td>
</tr>
</tbody>
</table>
<p><strong>List、Set 和 Map 如果想要根据两个对象的内容而不是地址比较是否相等时，需要重写 <code>equals()</code> 和 <code>hashCode()</code> 方法。<code>remove()</code>、<code>contains()</code>、<code>indexOf()</code> 等等方法都需要依赖它们。</strong></p>
<h1 id="abstractcollection抽象类">AbstractCollection抽象类</h1>
<p>AbstractCollection 抽象类是 Java 集合框架中 Collection 接口的一个直接实现类，Collection 下的大多数子类都继承 AbstractCollection抽象类，比如 List 的实现类、Set 的实现类。</p>
<p><strong>我们之所以可以使用 System.out.println() 直接输出集合的全部内容，而不用挨个遍历输出，全都是 AbstractCollection 中 toString() 方法的功劳。</strong></p>
<h1 id="arraylist类">ArrayList类</h1>
<blockquote>
<p>以数组实现的，遍历时很快，但插入、删除时都需要移动后面的元素，效率略差些。</p>
</blockquote>
<p>ArrayList 是 Java 集合框架中 List 接口的一个实现类。它可以说是我们使用最多的 List 集合，它有以下特点：</p>
<ul>
<li>容量不固定</li>
<li>有序（元素输出顺序与输入顺序一致）</li>
<li>元素可以为 <code>null</code></li>
<li>效率高
<ul>
<li>size()、isEmpty()、get()、set()、iterator()、listIterator() 方法的时间复杂度都是 O(1)</li>
<li>其他所有操作的时间复杂度几乎都是 O(n)</li>
</ul>
</li>
<li>占用空间更小：对比 LinkedList，不用占用额外空间维护链表结构</li>
</ul>
<p>ArrayList 继承自 RandomAccess，RandomAccess 是一个空的接口，用来标记某个类是否支持 <strong>随机访问</strong> （相比较于“按顺序访问”）。</p>
<h2 id="arraylist的成员变量">ArrayList的成员变量</h2>
<h3 id="1-底层数据结构数组">1、底层数据结构：数组</h3>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">transient</span> Object[] elementData;</span><br></pre></td></tr></table></figure>
<p>由于数组类型为 Object，所以允许添加 <code>null</code>。初始时该数组赋值为 <code>DEFAULTCAPACITY_EMPTY_ELEMENTDATA</code>。</p>
<blockquote>
<p>transient 说明这个数组无法序列化。</p>
</blockquote>
<h3 id="2-默认的空数组"><span id="emptyArray">2、默认的空数组</span></h3>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">final</span> Object[] EMPTY_ELEMENTDATA = &#123;&#125;;</span><br><span class="line"><span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">final</span> Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = &#123;&#125;;</span><br></pre></td></tr></table></figure>
<p>默认的空数组是 <code>DEFAULTCAPACITY_EMPTY_ELEMENTDATA</code>，它与 <code>EMPTY_ELEMENTDATA</code> 都是空数组，区别在于<strong>第一个元素被添加进数组时如何进行扩容</strong> ：</p>
<ul>
<li>如果初始的空数组是 <code>DEFAULTCAPACITY_EMPTY_ELEMENTDATA</code> 的话，第一个元素被添加进来后，数组 <code>elementData</code> 扩容到数组初始容量 <code>DEFAULT_CAPACITY = 10</code>。</li>
<li>如果初始的空数组是 <code>EMPTY_ELEMENTDATA</code> 的话，第一个元素被添加进来后，数组 <code>elementData</code> 扩容到容量为 <code>size(此时size = 0) + 1 = 1</code>。</li>
</ul>
<blockquote>
<p>可以观察 add() 方法来理解上面的话。</p>
</blockquote>
<h3 id="3-数组的初始容量为10">3、数组的初始容量为10</h3>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> DEFAULT_CAPACITY = <span class="number">10</span>;</span><br></pre></td></tr></table></figure>
<h3 id="4-数组中当前元素个数">4、数组中当前元素个数</h3>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">private</span> <span class="keyword">int</span> size;</span><br></pre></td></tr></table></figure>
<h3 id="5-数组最大容量">5、数组最大容量</h3>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> MAX_ARRAY_SIZE = Integer.MAX_VALUE - <span class="number">8</span>;</span><br></pre></td></tr></table></figure>
<h2 id="arraylist的关键方法">ArrayList的关键方法</h2>
<h3 id="1-构造函数">1、构造函数</h3>
<p>默认的无参构造，初始为空数组：</p>
<p>创建一个空 list，初始容量大小为 10。（创建完为空时 size 为0，当第一个元素被添加后容量大小为 10）</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="title">ArrayList</span><span class="params">()</span> </span>&#123;</span><br><span class="line">    <span class="keyword">this</span>.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>有参构造，根据指定容量， 创建对象数组：</p>
<p>当指定容量为 0 时，将用 <code>EMPTY_ELEMENTDATA</code> 来表示空数组，和无参构造的区别在于：第一个新元素加入后，数组进行扩容的方法不同。<code>EMPTY_ELEMENTDATA</code> 加入第一个新元素时数组容量加 1，具体参考 <a href="#emptyArray">AraayList的成员变量-&gt;2、默认的空数组</a></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="title">ArrayList</span><span class="params">(<span class="keyword">int</span> initialCapacity)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (initialCapacity &gt; <span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">this</span>.elementData = <span class="keyword">new</span> Object[initialCapacity];</span><br><span class="line">    &#125; <span class="keyword">else</span> <span class="keyword">if</span> (initialCapacity == <span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">this</span>.elementData = EMPTY_ELEMENTDATA;</span><br><span class="line">    &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">        <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">"Illegal Capacity: "</span>+</span><br><span class="line">                                           initialCapacity);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>有参构造，直接创建和指定集合一样内容的 ArrayList：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="title">ArrayList</span><span class="params">(Collection&lt;? extends E&gt; c)</span> </span>&#123;</span><br><span class="line">    elementData = c.toArray();</span><br><span class="line">    <span class="keyword">if</span> ((size = elementData.length) != <span class="number">0</span>) &#123;</span><br><span class="line">        <span class="comment">// c.toArray might (incorrectly) not return Object[] (see 6260652)</span></span><br><span class="line">        <span class="keyword">if</span> (elementData.getClass() != Object[].class)</span><br><span class="line">            elementData = Arrays.copyOf(elementData, size, Object[].class);</span><br><span class="line">    &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">        <span class="comment">// replace with empty array.</span></span><br><span class="line">        <span class="keyword">this</span>.elementData = EMPTY_ELEMENTDATA;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="2-添加元素">2、添加元素</h3>
<p>每次添加前会对数组的容量进行调整</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">add</span><span class="params">(E e)</span> </span>&#123;</span><br><span class="line">    ensureCapacityInternal(size + <span class="number">1</span>);  <span class="comment">// Increments modCount!!</span></span><br><span class="line">    elementData[size++] = e;</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="3-对数组容量进行调整">3、对数组容量进行调整</h3>
<p>可以主动调用 ensureCapacity() 方法来增加 list 的容量，避免每次元素满了时每次添加都需要等待扩容的的消耗。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">ensureCapacity</span><span class="params">(<span class="keyword">int</span> minCapacity)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)</span><br><span class="line">        <span class="comment">// 如果当前数组不是空数组 DEFAULTCAPACITY_EMPTY_ELEMENTDATA，那么当前最小容量为 0</span></span><br><span class="line">        ? <span class="number">0</span></span><br><span class="line">        <span class="comment">// 如果是空数组 DEFAULTCAPACITY_EMPTY_ELEMENTDATA，那么当前最小容量为默认容量 10</span></span><br><span class="line">        : DEFAULT_CAPACITY;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">if</span> (minCapacity &gt; minExpand) &#123;</span><br><span class="line">        <span class="comment">// 所需的最小容量大于当前最小容量，需要扩容</span></span><br><span class="line">        ensureExplicitCapacity(minCapacity);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">ensureCapacityInternal</span><span class="params">(<span class="keyword">int</span> minCapacity)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) &#123;</span><br><span class="line">        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    ensureExplicitCapacity(minCapacity);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">ensureExplicitCapacity</span><span class="params">(<span class="keyword">int</span> minCapacity)</span> </span>&#123;</span><br><span class="line">    modCount++;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// overflow-conscious code</span></span><br><span class="line">    <span class="keyword">if</span> (minCapacity - elementData.length &gt; <span class="number">0</span>)</span><br><span class="line">        grow(minCapacity);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="4-扩容">4、扩容</h3>
<p>默认每次扩容容量为旧容量的1.5倍。（如果是空 list，在第一个元素被添加进来后容量大小为默认容量大小 10）</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">grow</span><span class="params">(<span class="keyword">int</span> minCapacity)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> oldCapacity = elementData.length;</span><br><span class="line">    <span class="comment">// 新的容量 = 旧的容量 + 旧的容量 / 2 = 1.5 * 旧的容量</span></span><br><span class="line">    <span class="keyword">int</span> newCapacity = oldCapacity + (oldCapacity &gt;&gt; <span class="number">1</span>);</span><br><span class="line">    </span><br><span class="line">    <span class="comment">// 所需的最小容量大于旧容量的 1.5 倍</span></span><br><span class="line">    <span class="keyword">if</span> (newCapacity - minCapacity &lt; <span class="number">0</span>)</span><br><span class="line">        newCapacity = minCapacity;</span><br><span class="line">    </span><br><span class="line">    <span class="comment">// 新容量大于了最大容量</span></span><br><span class="line">    <span class="keyword">if</span> (newCapacity - MAX_ARRAY_SIZE &gt; <span class="number">0</span>)</span><br><span class="line">        newCapacity = hugeCapacity(minCapacity);</span><br><span class="line">    </span><br><span class="line">    <span class="comment">// minCapacity is usually close to size, so this is a win:</span></span><br><span class="line">    elementData = Arrays.copyOf(elementData, newCapacity);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">int</span> <span class="title">hugeCapacity</span><span class="params">(<span class="keyword">int</span> minCapacity)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (minCapacity &lt; <span class="number">0</span>) <span class="comment">// overflow</span></span><br><span class="line">        <span class="keyword">throw</span> <span class="keyword">new</span> OutOfMemoryError();</span><br><span class="line">    <span class="keyword">return</span> (minCapacity &gt; MAX_ARRAY_SIZE) ?</span><br><span class="line">        Integer.MAX_VALUE :</span><br><span class="line">        MAX_ARRAY_SIZE;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h1 id="queue接口队列">Queue接口，队列</h1>
<p>Java 集合中的 Queue 继承自 Collection 接口，Deque、LinkedList、PriorityQueue、BlockingQueue 等类都实现了它。</p>
<p>Queue 用来存放等待处理元素的集合，这种场景一般用于缓冲、并发访问。</p>
<h2 id="额外添加的api">额外添加的API</h2>
<table>
<thead>
<tr>
<th>操作</th>
<th>抛出异常</th>
<th>返回特殊值</th>
<th>用途</th>
</tr>
</thead>
<tbody>
<tr>
<td>插入</td>
<td>boolean add(e)</td>
<td>boolean offer(e)</td>
<td>在尾部添加（建议实现类禁止添加 null 元素，只有 LinkedList 类没有遵守）</td>
</tr>
<tr>
<td>删除</td>
<td>E remove()</td>
<td>E poll()</td>
<td>删除并返回头部</td>
</tr>
<tr>
<td>检查</td>
<td>E element()</td>
<td>E peek()</td>
<td>获取但不删除</td>
</tr>
</tbody>
</table>
<h2 id="为什么建议禁止添加-null-元素">为什么建议禁止添加 null 元素</h2>
<p>一般情况下 Queue 的实现类都不允许添加 <code>null</code> 元素，因为 poll()、peek() 方法在异常的时候会返回 <code>null</code>，如果你添加了 <code>null</code> 元素，当获取时不好分辨究竟是否正确返回。</p>
<h1 id="deque接口双端队列">Deque接口，双端队列</h1>
<p>Deque 接口继承自 Queue接口，直接实现了它的类有 LinkedList、ArayDeque、ConcurrentLinkedDeque 等。Deque 支持容量受限的双端队列，也支持大小不固定的。一般双端队列大小不确定。</p>
<p><img src="https://pic.tyzhang.top/images/2020/12/30/20161019193301571.png" alt="20161019193301571.png"></p>
<p>Deque 当队列用：</p>
<p><img src="https://pic.tyzhang.top/images/2020/12/30/20161019194500774.png" alt="20161019194500774.png"></p>
<p>Deque 当栈用：</p>
<p><img src="https://img-blog.csdn.net/20161019232902599" alt="这里写图片描述"></p>
<h2 id="deque-的实现类">Deque 的实现类</h2>
<ul>
<li>一般场景
<ul>
<li>LinkedList 大小可变的<strong>链表</strong>双端队列，允许元素为 <code>null</code></li>
<li>ArrayDeque 大小可变的<strong>数组</strong>双端队列，不允许元素为 <code>null</code></li>
</ul>
</li>
<li>并发场景
<ul>
<li>LinkedBlockingDeque 如果队列为空时，获取操作将会阻塞，直到有元素添加</li>
</ul>
</li>
</ul>
<h1 id="linkedlist类">LinkedList类</h1>
<p>LinkedList 继承自 AbstractSequentialList 接口，同时还实现了 Deque、Queue 接口。</p>
<blockquote>
<p>以链表实现的，插入、删除时只需要改变前后两个节点指针指向即可。</p>
</blockquote>
<h2 id="linkedlist双向链表实现">LinkedList双向链表实现</h2>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">LinkedList</span>&lt;<span class="title">E</span>&gt;</span></span><br><span class="line"><span class="class">    <span class="keyword">extends</span> <span class="title">AbstractSequentialList</span>&lt;<span class="title">E</span>&gt;</span></span><br><span class="line"><span class="class">    <span class="keyword">implements</span> <span class="title">List</span>&lt;<span class="title">E</span>&gt;, <span class="title">Deque</span>&lt;<span class="title">E</span>&gt;, <span class="title">Cloneable</span>, <span class="title">java</span>.<span class="title">io</span>.<span class="title">Serializable</span></span></span><br><span class="line"><span class="class"></span>&#123;</span><br><span class="line">    <span class="keyword">transient</span> <span class="keyword">int</span> size = <span class="number">0</span>;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * Pointer to first node.</span></span><br><span class="line"><span class="comment">     * Invariant: (first == null &amp;&amp; last == null) ||</span></span><br><span class="line"><span class="comment">     *            (first.prev == null &amp;&amp; first.item != null)</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">transient</span> Node&lt;E&gt; first;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * Pointer to last node.</span></span><br><span class="line"><span class="comment">     * Invariant: (first == null &amp;&amp; last == null) ||</span></span><br><span class="line"><span class="comment">     *            (last.next == null &amp;&amp; last.item != null)</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">transient</span> Node&lt;E&gt; last;</span><br></pre></td></tr></table></figure>
<p>LinkedList 的成员变量只有三个：</p>
<ul>
<li>size：容量</li>
<li>first：头节点</li>
<li>last：尾节点</li>
</ul>
<p>Node 类是一个双向节点：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">private</span> <span class="keyword">static</span> <span class="class"><span class="keyword">class</span> <span class="title">Node</span>&lt;<span class="title">E</span>&gt; </span>&#123;</span><br><span class="line">    E item;</span><br><span class="line">    Node&lt;E&gt; next;</span><br><span class="line">    Node&lt;E&gt; prev;</span><br><span class="line"></span><br><span class="line">    Node(Node&lt;E&gt; prev, E element, Node&lt;E&gt; next) &#123;</span><br><span class="line">        <span class="keyword">this</span>.item = element;</span><br><span class="line">        <span class="keyword">this</span>.next = next;</span><br><span class="line">        <span class="keyword">this</span>.prev = prev;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="linkedlist的方法">LinkedList的方法</h2>
<h3 id="1-关键的几个内部方法">1、关键的几个内部方法</h3>
<table>
<thead>
<tr>
<th>方法</th>
<th>用途</th>
</tr>
</thead>
<tbody>
<tr>
<td>void linkFirst(E e)</td>
<td>插入到头部</td>
</tr>
<tr>
<td>void linkLast(E e)</td>
<td>插入到尾部</td>
</tr>
<tr>
<td>void linkBefore(E e, Node<e> succ)</e></td>
<td>在指定节点 succ 前插入一个元素，假设 succ 不为 null</td>
</tr>
<tr>
<td>E unlinkFirst(Node<e> f)</e></td>
<td>删除头节点并返回该节点上的数据，假设不为 null</td>
</tr>
<tr>
<td>E unlinkLast(Node<e> l)</e></td>
<td>删除尾部节点并返回该节点上的数据，假设不为 null</td>
</tr>
<tr>
<td>E unlink(Node<e> x)</e></td>
<td>删除某个指定节点</td>
</tr>
<tr>
<td>Node<e> node(int index)</e></td>
<td>获取指定位置的节点</td>
</tr>
</tbody>
</table>
<p><strong>头部添加删除</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 插入到头部</span></span><br><span class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">linkFirst</span><span class="params">(E e)</span> </span>&#123;</span><br><span class="line">    <span class="comment">// 记录头节点</span></span><br><span class="line">    <span class="keyword">final</span> Node&lt;E&gt; f = first;</span><br><span class="line">    <span class="comment">// 新建一个节点，尾部指向之前的头节点 first</span></span><br><span class="line">    <span class="keyword">final</span> Node&lt;E&gt; newNode = <span class="keyword">new</span> Node&lt;&gt;(<span class="keyword">null</span>, e, f);</span><br><span class="line">    <span class="comment">// first 指向新的节点</span></span><br><span class="line">    first = newNode;</span><br><span class="line">	<span class="keyword">if</span> (f == <span class="keyword">null</span>)</span><br><span class="line">        <span class="comment">// 如果新建的是空链表，新建的节点也是最后一个节点</span></span><br><span class="line">        last = newNode;</span><br><span class="line">    <span class="keyword">else</span></span><br><span class="line">        <span class="comment">// 原来的第一个节点的头部指向新建的节点</span></span><br><span class="line">        f.prev = newNode;</span><br><span class="line">    size++;</span><br><span class="line">    modCount++;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 删除头节点并返回该节点上的数据，假设不为 null</span></span><br><span class="line"><span class="function"><span class="keyword">private</span> E <span class="title">unlinkFirst</span><span class="params">(Node&lt;E&gt; f)</span> </span>&#123;</span><br><span class="line">    <span class="comment">// assert f == first &amp;&amp; f != null;</span></span><br><span class="line">    <span class="keyword">final</span> E element = f.item;</span><br><span class="line">    <span class="keyword">final</span> Node&lt;E&gt; next = f.next;</span><br><span class="line">    f.item = <span class="keyword">null</span>;</span><br><span class="line">    f.next = <span class="keyword">null</span>; <span class="comment">// help GC</span></span><br><span class="line">    first = next;</span><br><span class="line">    <span class="keyword">if</span> (next == <span class="keyword">null</span>)</span><br><span class="line">        last = <span class="keyword">null</span>;</span><br><span class="line">    <span class="keyword">else</span></span><br><span class="line">        next.prev = <span class="keyword">null</span>;</span><br><span class="line">    size--;</span><br><span class="line">    modCount++;</span><br><span class="line">    <span class="keyword">return</span> element;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><strong>尾部添加删除</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 插入到尾部</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">linkLast</span><span class="params">(E e)</span> </span>&#123;</span><br><span class="line">    <span class="comment">// 记录尾节点</span></span><br><span class="line">    <span class="keyword">final</span> Node&lt;E&gt; l = last;</span><br><span class="line">    <span class="comment">// 新建一个节点，头部指向之前的尾节点 last</span></span><br><span class="line">    <span class="keyword">final</span> Node&lt;E&gt; newNode = <span class="keyword">new</span> Node&lt;&gt;(l, e, <span class="keyword">null</span>);</span><br><span class="line">    <span class="comment">// last 指向新的节点</span></span><br><span class="line">    last = newNode;</span><br><span class="line">    <span class="keyword">if</span> (l == <span class="keyword">null</span>)</span><br><span class="line">        <span class="comment">// 如果之前是空链表，新节点也是第一个节点</span></span><br><span class="line">        first = newNode;</span><br><span class="line">    <span class="keyword">else</span></span><br><span class="line">        <span class="comment">// 原来的尾节点尾部指向新的尾节点</span></span><br><span class="line">        l.next = newNode;</span><br><span class="line">    size++;</span><br><span class="line">    modCount++;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 删除尾部节点并返回，假设不会 null</span></span><br><span class="line"><span class="function"><span class="keyword">private</span> E <span class="title">unlinkLast</span><span class="params">(Node&lt;E&gt; l)</span> </span>&#123;</span><br><span class="line">    <span class="comment">// assert l == last &amp;&amp; l != null;</span></span><br><span class="line">    <span class="keyword">final</span> E element = l.item;</span><br><span class="line">    <span class="keyword">final</span> Node&lt;E&gt; prev = l.prev;</span><br><span class="line">    l.item = <span class="keyword">null</span>;</span><br><span class="line">    l.prev = <span class="keyword">null</span>; <span class="comment">// help GC</span></span><br><span class="line">    last = prev;</span><br><span class="line">    <span class="keyword">if</span> (prev == <span class="keyword">null</span>)</span><br><span class="line">        first = <span class="keyword">null</span>;</span><br><span class="line">    <span class="keyword">else</span></span><br><span class="line">        prev.next = <span class="keyword">null</span>;</span><br><span class="line">    size--;</span><br><span class="line">    modCount++;</span><br><span class="line">    <span class="keyword">return</span> element;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><strong>获取指定节点</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 获取指定位置的节点</span></span><br><span class="line"><span class="function">Node&lt;E&gt; <span class="title">node</span><span class="params">(<span class="keyword">int</span> index)</span> </span>&#123;</span><br><span class="line">    <span class="comment">// assert isElementIndex(index);</span></span><br><span class="line">	<span class="comment">// 二分，如果小于 size 的一半，从头开始遍历</span></span><br><span class="line">    <span class="keyword">if</span> (index &lt; (size &gt;&gt; <span class="number">1</span>)) &#123;</span><br><span class="line">        Node&lt;E&gt; x = first;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; index; i++)</span><br><span class="line">            x = x.next;</span><br><span class="line">        <span class="keyword">return</span> x;</span><br><span class="line">    &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">        Node&lt;E&gt; x = last;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = size - <span class="number">1</span>; i &gt; index; i--)</span><br><span class="line">            x = x.prev;</span><br><span class="line">        <span class="keyword">return</span> x;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><strong>指定节点的添加删除</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 在指定节点（不为 null）前插入一个元素</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">linkBefore</span><span class="params">(E e, Node&lt;E&gt; succ)</span> </span>&#123;</span><br><span class="line">    <span class="comment">// assert succ != null;</span></span><br><span class="line">    <span class="keyword">final</span> Node&lt;E&gt; pred = succ.prev;</span><br><span class="line">    <span class="comment">// 新建一个尾节点，头部指向 succ 前面的节点，尾部指向 succ 节点</span></span><br><span class="line">    <span class="keyword">final</span> Node&lt;E&gt; newNode = <span class="keyword">new</span> Node&lt;&gt;(pred, e, succ);</span><br><span class="line">    <span class="comment">// 让 succ 的头部指向新节点</span></span><br><span class="line">    succ.prev = newNode;</span><br><span class="line">    <span class="keyword">if</span> (pred == <span class="keyword">null</span>)</span><br><span class="line">        first = newNode;</span><br><span class="line">    <span class="keyword">else</span>	</span><br><span class="line">        pred.next = newNode;</span><br><span class="line">    size++;</span><br><span class="line">    modCount++;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 删除某个指定节点</span></span><br><span class="line"><span class="function">E <span class="title">unlink</span><span class="params">(Node&lt;E&gt; x)</span> </span>&#123;</span><br><span class="line">    <span class="comment">// assert x != null;</span></span><br><span class="line">    <span class="keyword">final</span> E element = x.item;</span><br><span class="line">    <span class="keyword">final</span> Node&lt;E&gt; next = x.next;</span><br><span class="line">    <span class="keyword">final</span> Node&lt;E&gt; prev = x.prev;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">if</span> (prev == <span class="keyword">null</span>) &#123;</span><br><span class="line">        first = next;</span><br><span class="line">    &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">        prev.next = next;</span><br><span class="line">        x.prev = <span class="keyword">null</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">if</span> (next == <span class="keyword">null</span>) &#123;</span><br><span class="line">        last = prev;</span><br><span class="line">    &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">        next.prev = prev;</span><br><span class="line">        x.next = <span class="keyword">null</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    x.item = <span class="keyword">null</span>;</span><br><span class="line">    size--;</span><br><span class="line">    modCount++;</span><br><span class="line">    <span class="keyword">return</span> element;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="2-常用的-api">2、常用的 API</h3>
<h4 id="添加方法">添加方法</h4>
<table>
<thead>
<tr>
<th>方法</th>
<th>用途</th>
</tr>
</thead>
<tbody>
<tr>
<td>boolean add(E e)</td>
<td>在尾部添加元素</td>
</tr>
<tr>
<td>void add(int index, E e)</td>
<td>在指定位置添加元素</td>
</tr>
<tr>
<td>boolean addAll(Collection&lt;? extends E&gt; c)</td>
<td>添加一个集合的元素</td>
</tr>
<tr>
<td>boolean addAll(int index, Collection&lt;? extends E&gt; c)</td>
<td>从指定的位置，添加一个集合的元素</td>
</tr>
<tr>
<td>void addFirst(E e)</td>
<td>在头部添加元素</td>
</tr>
<tr>
<td>void addLast(E e)</td>
<td>在尾部添加元素</td>
</tr>
</tbody>
</table>
<h4 id="删除方法">删除方法</h4>
<table>
<thead>
<tr>
<th>方法</th>
<th>用途</th>
</tr>
</thead>
<tbody>
<tr>
<td>E remove()</td>
<td>删除头部节点</td>
</tr>
<tr>
<td>E remove(int index)</td>
<td>删除指定位置节点</td>
</tr>
<tr>
<td>boolean remove(Object o)</td>
<td>删除包含指定元素的节点（遍历）</td>
</tr>
<tr>
<td>E removeFirst()</td>
<td>删除头部节点</td>
</tr>
<tr>
<td>E removeLset()</td>
<td>删除尾部节点</td>
</tr>
<tr>
<td>boolean removeFirstOccurrence(Object o)</td>
<td>删除首次出现的指定元素（从头节点开始遍历）</td>
</tr>
<tr>
<td>boolean removeLastOccurrence(Object o)</td>
<td>删除最后一次出现的指定元素（从尾部节点开始遍历）</td>
</tr>
<tr>
<td>void clear</td>
<td>清除全部元素</td>
</tr>
</tbody>
</table>
<h4 id="修改方法">修改方法</h4>
<table>
<thead>
<tr>
<th>方法</th>
<th>用途</th>
</tr>
</thead>
<tbody>
<tr>
<td>E set(int index, E e)</td>
<td>修改指定位置的元素</td>
</tr>
</tbody>
</table>
<h4 id="查询方法">查询方法</h4>
<table>
<thead>
<tr>
<th>方法</th>
<th>用途</th>
</tr>
</thead>
<tbody>
<tr>
<td>int indexOf(Object o)</td>
<td>获取指定元素第一次出现的位置</td>
</tr>
<tr>
<td>int lastIndexOf(Object o)</td>
<td>获取指定元素最后一次出现的位置（倒着遍历）</td>
</tr>
<tr>
<td>boolean contains(Object o)</td>
<td>是否包含指定元素</td>
</tr>
<tr>
<td>E get(int index)</td>
<td>获取指定位置的元素</td>
</tr>
<tr>
<td>E getFirst()</td>
<td>获取第一个元素</td>
</tr>
<tr>
<td>E poll()</td>
<td>获取第一个元素，同时删除它</td>
</tr>
<tr>
<td>E peek()</td>
<td>获取第一个元素</td>
</tr>
<tr>
<td>E peekFirst()</td>
<td>获取第一个元素</td>
</tr>
<tr>
<td>E getLast()</td>
<td>获取最后一个元素</td>
</tr>
<tr>
<td>E peekLast()</td>
<td>获取最后一个元素</td>
</tr>
<tr>
<td></td>
<td></td>
</tr>
</tbody>
</table>
<h1 id="arraylist和linkedlist的比较">ArrayList和LinkedList的比较</h1>
<p>ArrayList：</p>
<ul>
<li>基于数组，在数组中搜索和读取数据是很快的。因此 ArrayList 获取数据的时间复杂度是O(1);</li>
<li>但是添加、删除时该元素后面的所有元素都要移动，所以添加/删除数据效率不高；</li>
<li>另外其实还是有容量的，每次达到阈值需要扩容，这个操作比较影响效率。</li>
</ul>
<p>LinkedList：</p>
<ul>
<li>基于双端链表，添加/删除元素只会影响周围的两个节点，开销很低；</li>
<li>只能顺序遍历，无法按照索引获得元素，因此查询效率不高；</li>
<li>没有固定容量，不需要扩容；</li>
<li>需要更多的内存，LinkedList 每个节点中需要多存储前后节点的信息，占用空间更多些。</li>
</ul>
<h1 id="vector类">Vector类</h1>
<p>Vector 类被认为是线程安全的 ArrayList，和 ArrayList 一样也是继承自 AbstractList。它是 Stack 的父类。</p>
<h2 id="成员变量">成员变量</h2>
<p><strong>1、底层也是个数组</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">protected</span> Object[] elementData;</span><br></pre></td></tr></table></figure>
<p>2、<strong>数组元素个数</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">protected</span> <span class="keyword">int</span> elementCount;</span><br></pre></td></tr></table></figure>
<p>3、<strong>扩容时增长数量</strong></p>
<p>允许用户自己设置，如果这个值为 0 或者负数，扩容时会扩大 2 倍，而不是 1.5 倍。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">protected</span> <span class="keyword">int</span> capacityIncrement;</span><br></pre></td></tr></table></figure>
<h2 id="vector特点">Vector特点</h2>
<ul>
<li>底层由一个可以增长的数组组成</li>
<li>Vector 通过 capacity 和 capacityIncrement 来尽量少的占用空间</li>
<li>扩容时默认扩大两倍</li>
<li>最好在插入大量元素前增加 vector 的容量，以减少重新申请内存的次数</li>
<li>同步类，每个方法前都有同步锁 synchronized</li>
</ul>
<h1 id="vector和arraylist的比较">Vector和ArrayList的比较</h1>
<p>共同点：</p>
<ul>
<li>都是基于数组的</li>
<li>都支持随机访问</li>
<li>默认容量都是 10</li>
<li>都有扩容机制</li>
</ul>
<p>区别：</p>
<ul>
<li>Vector（JDK 1.0） 早于 ArrayList （JDK 1.2）出现</li>
<li>Vector 比 ArrayList 多一种迭代器 Enumeration（该迭代器不是 fail-fast 的）</li>
<li>Vector 是线程安全的，ArrayList 不是</li>
<li>Vector 默认扩容 2 倍，ArrayList 是 1.5 倍</li>
</ul>
<h1 id="stack栈">Stack栈</h1>
<p>Stack 集成自 Vector，是由数组实现的栈。</p>
<h2 id="stack的方法">Stack的方法</h2>
<table>
<thead>
<tr>
<th>方法</th>
<th>用途</th>
</tr>
</thead>
<tbody>
<tr>
<td>Stack()</td>
<td>构建一个空栈</td>
</tr>
<tr>
<td>E push(E item)</td>
<td>入栈，调用的是 Vector.addElemnt()</td>
</tr>
<tr>
<td>synchronized E peek()</td>
<td>获取顶端元素，但不删除，调用的是 Vector.elementAt()</td>
</tr>
<tr>
<td>synchronized E pop()</td>
<td>出栈，调用 Vector.removeElementAt() 删除顶端元素</td>
</tr>
<tr>
<td>synchronized int search(Object o)</td>
<td>查找元素是否在栈中，返回栈顶到该元素出现的位置的距离</td>
</tr>
<tr>
<td>boolean empty()</td>
<td>栈是否为空</td>
</tr>
</tbody>
</table>
<h1 id="map接口">Map接口</h1>
<p>Map 接口是和 Collection 接口同一等级的集合根接口，它表示一个键值对（key-value）的映射。</p>
<p>Map 中元素的顺序取决于迭代器迭代时的顺序，有的实现类保证了元素输入输出时的顺序（TreeMap），有的实现类则是无序的（HashMap）。</p>
<h2 id="视图">视图</h2>
<p>Map 接口提供了三个角度来分析 Map：</p>
<ul>
<li>KeySet——Set</li>
<li>Values——Collection</li>
<li>Entry——Set</li>
</ul>
<h3 id="keyset">KeySet</h3>
<p>KeySet 是一个 Map 中键（Key）的集合，以 Set 的形式保存，不允许重复，因此键存储的对象需要重写 equals() 和 hashCode() 方法。</p>
<p>可以通过 Map.keySet() 方法获得。</p>
<h3 id="values">Values</h3>
<p>Values 是一个 Mao 中值（value）的集合，以 Collection 的形式保存，因此可以重复。</p>
<p>通过 Map.values() 方法获得。</p>
<h3 id="entry">Entry</h3>
<p>Entry 是 Map 接口中的静态内部接口，表示一个键值对的映射。</p>
<p><strong>Entry的方法</strong></p>
<table>
<thead>
<tr>
<th>方法</th>
<th>用途</th>
</tr>
</thead>
<tbody>
<tr>
<td>K getKey()</td>
<td>获取这组映射中的键 key</td>
</tr>
<tr>
<td>V getValue()</td>
<td>获取这组映射中的值 value</td>
</tr>
<tr>
<td>V setValue()</td>
<td>修改这组映射中的值</td>
</tr>
<tr>
<td>int hashCode()</td>
<td>返回这个 Entry 的哈希值</td>
</tr>
<tr>
<td>boolean equals()</td>
<td>对比 key-value 是否相等</td>
</tr>
</tbody>
</table>
<p>通过 Map.entrySet() 方法获得的是一组 Entry 集合，保存在 Set 中，所以 Map 中的 Entry 也不能重复。</p>
<h2 id="map的三种遍历方式">Map的三种遍历方式</h2>
<p>根据 Map 提供的三种视图，可以由三种遍历方式。</p>
<h3 id="1-使用-keyset-遍历">1、使用 KeySet 遍历</h3>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">Set set = map.keySet();</span><br><span class="line"><span class="keyword">for</span> (Object key : set) &#123;</span><br><span class="line">    System.out.println(map.get(key));</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="2-使用-values-遍历">2、使用 Values 遍历</h3>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">Collection values = map.values();</span><br><span class="line">Iterator iterator = values.iterator();</span><br><span class="line"><span class="keyword">while</span> (iterator.hasNext()) &#123;</span><br><span class="line">    System.out.println(<span class="string">"value"</span> + iterator.next());</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="3-使用-entry-遍历">3、使用 Entry 遍历</h3>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line">Set entrySet = map.entrySet();</span><br><span class="line"><span class="keyword">for</span> (Object o : entrySet) &#123;</span><br><span class="line">    Map.Entry entry = (Map.Entry) o;</span><br><span class="line">    System.out.println(entry); <span class="comment">// key = value</span></span><br><span class="line">    System.out.println(entry.getKey() + <span class="string">"/"</span> + entry.getValue());</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="map的实现类">Map的实现类</h2>
<p><img src="https://pic.tyzhang.top/images/2021/01/04/image.png" alt="image.png"></p>
<p>Map 的实现类主要有 4 种：</p>
<ul>
<li>Hashtable：古老，线程安全</li>
<li>HashMap：速度很快，但没有顺序</li>
<li>TreeMap：有序的，效率比 HashMap 慢</li>
<li>LinkedHashMap：结合 HashMap 和 TreeMap 的优点，有序的同时效率也不错，仅比 HashMap 慢一点。</li>
</ul>
<blockquote>
<p>可以使用 Map 作为  Map 的值，但禁止使用 Map 作为 Map 的键。因为复杂的 Map 中 equals() 和 hashCode() 方法比较难定义。</p>
</blockquote>
<h1 id="hashmap">HashMap</h1>
<p>HashMap 是一个采用哈希表实现的键值对集合，底层实现是数组 + 链表。</p>
<h2 id="hashmap的特点">HashMap的特点：</h2>
<ul>
<li>底层实现是链表数组，JDK 8 之后加了红黑树</li>
<li>实现了 Map 的全部方法</li>
<li>key 用 Set 存放，所以想做到 key 不允许重复，key 对应的类需要重写  equals() 和 hashCode() 方法</li>
<li>允许空键和空值（但空键只有一个，且放在第一位）</li>
<li>元素是无序的，而且顺序会不定时改变</li>
<li>插入、获取的时间复杂度基本是 O(1)（有个前提是有适当的哈希函数，让元素分布在均匀的位置）</li>
<li>遍历整个 Map 需要的时间与桶（数组）的长度成正比（因此初始化时 HashMap 的容量不宜太大）</li>
<li>两个关键因子：初始容量、加载因子</li>
</ul>
<h2 id="hashmap的成员变量">HashMap的成员变量</h2>
<p>1、默认初始容量：16，必须是 2 的整数次方，<a href="#whyHashValue">原因点击这里</a></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> DEFAULT_INITIAL_CAPACITY = <span class="number">1</span> &lt;&lt; <span class="number">4</span>; <span class="comment">// aka 16</span></span><br></pre></td></tr></table></figure>
<p>2、默认的加载因子的大小：0.75（该大小是结合时间和空间效率考虑得到的）</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">float</span> DEFAULT_LOAD_FACTOR = <span class="number">0.75f</span>;</span><br></pre></td></tr></table></figure>
<p>3、最大容量：$2^{30}$</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> MAXIMUM_CAPACITY = <span class="number">1</span> &lt;&lt; <span class="number">30</span>;</span><br></pre></td></tr></table></figure>
<p>4、当前 HashMap 修改的次数，这个变量用来保证 fail-fast 机制</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">transient</span> <span class="keyword">int</span> modCount;</span><br></pre></td></tr></table></figure>
<p>5、阈值、下次需要扩容时的值，等于 容量 * 加载因子</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">int</span> threshold;</span><br></pre></td></tr></table></figure>
<p>6、树形阈值：JDK 1.8 新增的，当容量超过 8 之后，使用树而不是链表来作为桶，必须大于 2</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> TREEIFY_THRESHOLD = <span class="number">8</span>;</span><br></pre></td></tr></table></figure>
<p>7、非树形阈值：JDK 1.8 新增的，扩容时如果发现桶中长度小于 6 ，则会由树重写退化为链表</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> UNTREEIFY_THRESHOLD = <span class="number">6</span>;</span><br></pre></td></tr></table></figure>
<p>8、树形最小容量：当 HashMap 的容量大于该值时，才允许树形化链表（即将链表转换成红黑树），否则若桶内元素太多时则直接进行扩容。（为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD）</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> MIN_TREEIFY_CAPACITY = <span class="number">64</span>;</span><br></pre></td></tr></table></figure>
<blockquote>
<p>当桶中的数量小于 TREEIFY_THRESHOLD 时不会转换成树形结构存储；如果桶中的数量大于 TREEIFY_THRESHOLD，但 capacity 小于 MIN_TREEIFY_CAPACITY 则依然使用单链表结构进行存储，此时会对 HashMap 进行扩容；如果 capacity 大于了 MIN_TREEIFY_CAPACITY 则会进行树化。</p>
</blockquote>
<p>9、缓存的键值对集合（另外两个视图：KeySet 和 Values 在 AbstractMap 中声明的）</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">transient</span> Set&lt;Map.Entry&lt;K,V&gt;&gt; entrySet;</span><br></pre></td></tr></table></figure>
<p>10、哈希表中的链表数组</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">transient</span> Node&lt;K,V&gt;[] table;</span><br></pre></td></tr></table></figure>
<p>11、键值对的数量</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">transient</span> <span class="keyword">int</span> size;</span><br></pre></td></tr></table></figure>
<p>12、哈希表的加载因子</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">final</span> <span class="keyword">float</span> loadFactor;</span><br></pre></td></tr></table></figure>
<h2 id="hashmap的初始容量和加载因子">HashMap的初始容量和加载因子</h2>
<p>由于 HashMap 扩容开销很大（需要创建新数组、重新分配哈希、分配等等），因此与扩容相关的两个因素：</p>
<ul>
<li>容量：数组的容量</li>
<li>加载因子：决定了 HashMap 中的元素占有多少比例时扩容</li>
</ul>
<p>HashMap 的默认加载因子为 0.75，这是在时间、空间两方面均衡考虑下的结果：</p>
<ul>
<li>加载因子太大的话发生冲突的可能就会变大，查找的效率反而低</li>
<li>太小的话频繁 rehash，导致性能降低</li>
</ul>
<p>当设置初始容量时，需要提前考虑 Map 中可能有多少对键值对，设计合理的加载因子，尽可能避免进行扩容。</p>
<p>如果存储的键值对很多，干脆直接设置一个大点的容量，这样可以少扩容几次。</p>
<blockquote>
<p>阈值 = 容量 * 加载因子</p>
</blockquote>
<h2 id="hashmap-中的链表节点">HashMap 中的链表节点</h2>
<p>HashMap 的底层数据结构之一（JDK 1.8 之前单纯是）是链表数组：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">transient</span> Node&lt;K,V&gt;[] table;</span><br></pre></td></tr></table></figure>
<p>每一个链表节点如下：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">static</span> <span class="class"><span class="keyword">class</span> <span class="title">Node</span>&lt;<span class="title">K</span>,<span class="title">V</span>&gt; <span class="keyword">implements</span> <span class="title">Map</span>.<span class="title">Entry</span>&lt;<span class="title">K</span>,<span class="title">V</span>&gt; </span>&#123;</span><br><span class="line">    <span class="comment">// 哈希值，即位置</span></span><br><span class="line">    <span class="keyword">final</span> <span class="keyword">int</span> hash;</span><br><span class="line">    <span class="comment">// 键</span></span><br><span class="line">    <span class="keyword">final</span> K key;</span><br><span class="line">	<span class="comment">// 值</span></span><br><span class="line">    V value;</span><br><span class="line">    <span class="comment">// 指向下一个节点的指针</span></span><br><span class="line">    Node&lt;K,V&gt; next;</span><br><span class="line"></span><br><span class="line">    Node(<span class="keyword">int</span> hash, K key, V value, Node&lt;K,V&gt; next) &#123;</span><br><span class="line">        <span class="keyword">this</span>.hash = hash;</span><br><span class="line">        <span class="keyword">this</span>.key = key;</span><br><span class="line">        <span class="keyword">this</span>.value = value;</span><br><span class="line">        <span class="keyword">this</span>.next = next;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">final</span> K <span class="title">getKey</span><span class="params">()</span>        </span>&#123; <span class="keyword">return</span> key; &#125;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">final</span> V <span class="title">getValue</span><span class="params">()</span>      </span>&#123; <span class="keyword">return</span> value; &#125;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">final</span> String <span class="title">toString</span><span class="params">()</span> </span>&#123; <span class="keyword">return</span> key + <span class="string">"="</span> + value; &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">final</span> <span class="keyword">int</span> <span class="title">hashCode</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> Objects.hashCode(key) ^ Objects.hashCode(value);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">final</span> V <span class="title">setValue</span><span class="params">(V newValue)</span> </span>&#123;</span><br><span class="line">        V oldValue = value;</span><br><span class="line">        value = newValue;</span><br><span class="line">        <span class="keyword">return</span> oldValue;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">final</span> <span class="keyword">boolean</span> <span class="title">equals</span><span class="params">(Object o)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (o == <span class="keyword">this</span>)</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">        <span class="keyword">if</span> (o <span class="keyword">instanceof</span> Map.Entry) &#123;</span><br><span class="line">            <span class="comment">// Map.Entry 相等的条件：键相等、值相等</span></span><br><span class="line">            Map.Entry&lt;?,?&gt; e = (Map.Entry&lt;?,?&gt;)o;</span><br><span class="line">            <span class="keyword">if</span> (Objects.equals(key, e.getKey()) &amp;&amp;</span><br><span class="line">                Objects.equals(value, e.getValue()))</span><br><span class="line">                <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="hashmap中的添加操作">▲HashMap中的添加操作</h2>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 添加指定的键值对到 Map 中，如果已经存在则替换</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> V <span class="title">put</span><span class="params">(K key, V value)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">return</span> putVal(hash(key), key, value, <span class="keyword">false</span>, <span class="keyword">true</span>);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">final</span> V <span class="title">putVal</span><span class="params">(<span class="keyword">int</span> hash, K key, V value, <span class="keyword">boolean</span> onlyIfAbsent,</span></span></span><br><span class="line"><span class="function"><span class="params">               <span class="keyword">boolean</span> evict)</span> </span>&#123;</span><br><span class="line">    Node&lt;K,V&gt;[] tab; Node&lt;K,V&gt; p; <span class="keyword">int</span> n, i;</span><br><span class="line">    <span class="comment">// 如果哈希表为空或，则 ？扩容？</span></span><br><span class="line">    <span class="keyword">if</span> ((tab = table) == <span class="keyword">null</span> || (n = tab.length) == <span class="number">0</span>)</span><br><span class="line">        n = (tab = resize()).length;</span><br><span class="line">    <span class="comment">// 如果要插入的位置没有元素，则新创建一个节点插入</span></span><br><span class="line">    <span class="keyword">if</span> ((p = tab[i = (n - <span class="number">1</span>) &amp; hash]) == <span class="keyword">null</span>)</span><br><span class="line">        tab[i] = newNode(hash, key, value, <span class="keyword">null</span>);</span><br><span class="line">    <span class="keyword">else</span> &#123;</span><br><span class="line">        <span class="comment">// 如果要插入的桶已经有元素，那么用 e 指向被替换的元素</span></span><br><span class="line">        Node&lt;K,V&gt; e; K k;</span><br><span class="line">        <span class="comment">// 此时 p 是桶中的第一个元素，如果 p 的 hash、key 和要插入的元素相同</span></span><br><span class="line">        <span class="comment">// 那么用 e 指向 p</span></span><br><span class="line">        <span class="keyword">if</span> (p.hash == hash &amp;&amp;</span><br><span class="line">            ((k = p.key) == key || (key != <span class="keyword">null</span> &amp;&amp; key.equals(k))))</span><br><span class="line">            e = p;</span><br><span class="line">        <span class="comment">// 如果不同，且 p 是 JDK 1.8 之后的树形节点，那么调用 putTreeVal() 函数进行插入</span></span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> (p <span class="keyword">instanceof</span> TreeNode)</span><br><span class="line">            e = ((TreeNode&lt;K,V&gt;)p).putTreeVal(<span class="keyword">this</span>, tab, hash, key, value);</span><br><span class="line">        <span class="comment">// 否则按照传统的遍历链表方法进行查找、替换</span></span><br><span class="line">        <span class="keyword">else</span> &#123;</span><br><span class="line">            <span class="comment">// 遍历这个桶中所有元素</span></span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> binCount = <span class="number">0</span>; ; ++binCount) &#123;</span><br><span class="line">                <span class="comment">// 如果遍历到桶的最后一个元素还未找到，那么在桶的末尾插入该元素</span></span><br><span class="line">                <span class="keyword">if</span> ((e = p.next) == <span class="keyword">null</span>) &#123;</span><br><span class="line">                    p.next = newNode(hash, key, value, <span class="keyword">null</span>);</span><br><span class="line">                    <span class="comment">// 如果桶中的元素大于等于 8 ，则需要将桶进行树形化</span></span><br><span class="line">                    <span class="comment">// 这里大于等于 7 是因为 binCount 从 0 开始计数的</span></span><br><span class="line">                    <span class="keyword">if</span> (binCount &gt;= TREEIFY_THRESHOLD - <span class="number">1</span>) <span class="comment">// -1 for 1st</span></span><br><span class="line">                        treeifyBin(tab, hash);</span><br><span class="line">                    <span class="keyword">break</span>;</span><br><span class="line">                &#125;</span><br><span class="line">                <span class="comment">// 如果找到了则停止，e 已经指向了要被替换的元素</span></span><br><span class="line">                <span class="keyword">if</span> (e.hash == hash &amp;&amp;</span><br><span class="line">                    ((k = e.key) == key || (key != <span class="keyword">null</span> &amp;&amp; key.equals(k))))</span><br><span class="line">                    <span class="keyword">break</span>;</span><br><span class="line">                p = e;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 如果找到了</span></span><br><span class="line">        <span class="keyword">if</span> (e != <span class="keyword">null</span>) &#123; <span class="comment">// existing mapping for key</span></span><br><span class="line">            V oldValue = e.value;</span><br><span class="line">            <span class="comment">// 替换，返回</span></span><br><span class="line">            <span class="keyword">if</span> (!onlyIfAbsent || oldValue == <span class="keyword">null</span>)</span><br><span class="line">                e.value = value;</span><br><span class="line">            afterNodeAccess(e);</span><br><span class="line">            <span class="keyword">return</span> oldValue;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    ++modCount;</span><br><span class="line">    <span class="comment">// 如果超出阈值，扩容</span></span><br><span class="line">    <span class="keyword">if</span> (++size &gt; threshold)</span><br><span class="line">        resize();</span><br><span class="line">    afterNodeInsertion(evict);</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><strong>根据代码总结插入逻辑：</strong></p>
<ol>
<li>调用 hash() 方法计算键 key 所对应的哈希值</li>
<li>调用 putVal() 方法根据哈希值进行相关操作</li>
<li>如果当前的哈希表内容为空，新建一个哈希表</li>
<li>如果要插入的桶中没有元素，新建一个节点并放入桶中</li>
<li>否则从桶中第一个元素开始查找哈希值对应位置
<ol>
<li>如果桶中第一个元素的哈希值和要添加元素的哈希值一样，替换，结束查找</li>
<li>如果桶中第一个元素的哈希值和要添加元素的哈希值不一样，而且当前采用的是 JDK 8 以后的树形节点，则调用 putTreeVal() 进行插入</li>
<li>否则还是用传统的链表遍历方法进行查找、替换，结束查找</li>
<li>当这个桶中元素个数大于等于 8 时，调用 treeifyBin() 方法进行树形化</li>
</ol>
</li>
<li>检查是否需要扩容</li>
</ol>
<p>插入过程中的几个关键的其他方法：</p>
<ul>
<li>hash()：计算键 key 在哈希表中对应的位置</li>
<li>resize()：扩容</li>
<li>putTreeVal()：树形节点的插入</li>
<li>treeifyBin()：对桶进行树形化</li>
</ul>
<h2 id="hashmap中的哈希函数hash">▲HashMap中的哈希函数hash()</h2>
<p>HashMap 中通过把传入键的 hashCode 和 hashCode 无符号右移 16 位得到的结果进行按位异或，得到这个键的哈希值。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> <span class="title">hash</span><span class="params">(Object key)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> h;</span><br><span class="line">    <span class="keyword">return</span> (key == <span class="keyword">null</span>) ? <span class="number">0</span> : (h = key.hashCode()) ^ (h &gt;&gt;&gt; <span class="number">16</span>);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>由于哈希表的容量都是 <strong>2 的 N 次方</strong>，元素的 hashCode() 在很多时候下低位（二进制下）是相同的，这将容易导致冲突（碰撞），因此 JDK 1.8 之后添加了一个位移操作：将元素的 hashCode() 和自己无符号右移 16 位后的结果求异或。<a href="#hashWhy">为什么这样实现 hash()</a></p>
<p>这样可以避免只靠低位数据来计算哈希时容易导致冲突，计算结果由高低位结合决定，可以避免哈希值分布不均匀。且采用位运算效率更高。</p>
<h2 id="hashmap中的初始化扩容方法resize">▲HashMap中的初始化/扩容方法resize()</h2>
<p>HashMap 每次添加时会比较当前元素个数和阈值，如果超出阈值就需要进行扩容：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">if</span> (++size &gt; threshold)</span><br><span class="line">    resize();</span><br></pre></td></tr></table></figure>
<p><strong>扩容</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">final</span> Node&lt;K,V&gt;[] resize() &#123;</span><br><span class="line">    Node&lt;K,V&gt;[] oldTab = table;</span><br><span class="line">    <span class="comment">// 旧哈希表的容量</span></span><br><span class="line">    <span class="keyword">int</span> oldCap = (oldTab == <span class="keyword">null</span>) ? <span class="number">0</span> : oldTab.length;</span><br><span class="line">    <span class="comment">// 旧哈希表的阈值</span></span><br><span class="line">    <span class="keyword">int</span> oldThr = threshold;</span><br><span class="line">    <span class="keyword">int</span> newCap, newThr = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">if</span> (oldCap &gt; <span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">if</span> (oldCap &gt;= MAXIMUM_CAPACITY) &#123;</span><br><span class="line">            threshold = Integer.MAX_VALUE;</span><br><span class="line">            <span class="keyword">return</span> oldTab;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 新的容量 = 旧容量 * 2</span></span><br><span class="line">        <span class="comment">// 新的阈值 = 旧阈值 * 2</span></span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> ((newCap = oldCap &lt;&lt; <span class="number">1</span>) &lt; MAXIMUM_CAPACITY &amp;&amp;</span><br><span class="line">                 oldCap &gt;= DEFAULT_INITIAL_CAPACITY)</span><br><span class="line">            newThr = oldThr &lt;&lt; <span class="number">1</span>; <span class="comment">// double threshold</span></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 旧容量为 0 且 旧阈值大于 0，说明之前创建了哈希表但是没有添加元素</span></span><br><span class="line">    <span class="comment">// 那么初始化容量为阈值</span></span><br><span class="line">    <span class="keyword">else</span> <span class="keyword">if</span> (oldThr &gt; <span class="number">0</span>) <span class="comment">// initial capacity was placed in threshold</span></span><br><span class="line">        newCap = oldThr;</span><br><span class="line">    <span class="comment">// 旧容量、旧阈值都是 0，说明还没创建哈希表，容量为默认容量 16，阈值为 容量*加载因子</span></span><br><span class="line">    <span class="keyword">else</span> &#123;               <span class="comment">// zero initial threshold signifies using defaults</span></span><br><span class="line">        newCap = DEFAULT_INITIAL_CAPACITY;</span><br><span class="line">        newThr = (<span class="keyword">int</span>)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 如果新阈值为 0 ，需要用 新容量*加载因子 重新算一遍</span></span><br><span class="line">    <span class="keyword">if</span> (newThr == <span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">float</span> ft = (<span class="keyword">float</span>)newCap * loadFactor;</span><br><span class="line">        newThr = (newCap &lt; MAXIMUM_CAPACITY &amp;&amp; ft &lt; (<span class="keyword">float</span>)MAXIMUM_CAPACITY ?</span><br><span class="line">                  (<span class="keyword">int</span>)ft : Integer.MAX_VALUE);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 更新阈值</span></span><br><span class="line">    threshold = newThr;</span><br><span class="line">    <span class="comment">// 创建新的哈希表，容量为原来容量的两倍</span></span><br><span class="line">    <span class="comment">// 如果之前没有创建哈希表，那么容量为默认容量 16</span></span><br><span class="line">    <span class="meta">@SuppressWarnings</span>(&#123;<span class="string">"rawtypes"</span>,<span class="string">"unchecked"</span>&#125;)</span><br><span class="line">        Node&lt;K,V&gt;[] newTab = (Node&lt;K,V&gt;[])<span class="keyword">new</span> Node[newCap];</span><br><span class="line">    table = newTab;</span><br><span class="line">    <span class="comment">// 如果旧哈希表中有数据，则进行遍历复制</span></span><br><span class="line">    <span class="comment">// 低位链表存放在扩容之后的下标位置，与当前数组的下标位置一致</span></span><br><span class="line">    <span class="comment">// 高位链存放在当前数组下标位置+扩容之前的数组长度</span></span><br><span class="line">    <span class="keyword">if</span> (oldTab != <span class="keyword">null</span>) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; oldCap; ++j) &#123;</span><br><span class="line">            Node&lt;K,V&gt; e;</span><br><span class="line">            <span class="comment">// 旧的桶不为空，用 e 指向旧的桶</span></span><br><span class="line">            <span class="keyword">if</span> ((e = oldTab[j]) != <span class="keyword">null</span>) &#123;</span><br><span class="line">                <span class="comment">// 将旧的桶置为空释放</span></span><br><span class="line">                oldTab[j] = <span class="keyword">null</span>;</span><br><span class="line">                <span class="comment">// 如果旧的桶只有一个元素，那么直接在新的桶的对应位置赋值</span></span><br><span class="line">                <span class="keyword">if</span> (e.next == <span class="keyword">null</span>)</span><br><span class="line">                    newTab[e.hash &amp; (newCap - <span class="number">1</span>)] = e;</span><br><span class="line">                <span class="comment">// 如果旧的哈希表当前位置是树形节点，则新的哈希表当前位置也需要变成树形结构</span></span><br><span class="line">                <span class="keyword">else</span> <span class="keyword">if</span> (e <span class="keyword">instanceof</span> TreeNode)</span><br><span class="line">                    ((TreeNode&lt;K,V&gt;)e).split(<span class="keyword">this</span>, newTab, j, oldCap);</span><br><span class="line">				<span class="comment">// 保留旧的桶中的顺序复制到新的桶中</span></span><br><span class="line">                <span class="keyword">else</span> &#123; <span class="comment">// preserve order</span></span><br><span class="line">                    <span class="comment">// 设置低位首节点和低位尾节点</span></span><br><span class="line">                    Node&lt;K,V&gt; loHead = <span class="keyword">null</span>, loTail = <span class="keyword">null</span>;</span><br><span class="line">                    <span class="comment">// 设置高位首节点和高位尾节点</span></span><br><span class="line">                    Node&lt;K,V&gt; hiHead = <span class="keyword">null</span>, hiTail = <span class="keyword">null</span>;</span><br><span class="line">                    Node&lt;K,V&gt; next;</span><br><span class="line">                    <span class="keyword">do</span> &#123;</span><br><span class="line">                        next = e.next;</span><br><span class="line">                        <span class="comment">// 做一个按位与的运算</span></span><br><span class="line">                        <span class="keyword">if</span> ((e.hash &amp; oldCap) == <span class="number">0</span>) &#123;</span><br><span class="line">                            <span class="comment">// 如果低位尾节点为 null 的话，说明还没开始遍历这个桶下的链表，就把 e 赋值给低位首节点</span></span><br><span class="line">                            <span class="keyword">if</span> (loTail == <span class="keyword">null</span>)</span><br><span class="line">                                loHead = e;</span><br><span class="line">                            <span class="comment">// 否则低位尾节点不为 null 的话，说明已经在遍历了  </span></span><br><span class="line">                            <span class="keyword">else</span></span><br><span class="line">                                loTail.next = e;</span><br><span class="line">                            loTail = e;</span><br><span class="line">                        &#125;</span><br><span class="line">                        <span class="comment">// 如果 e 节点的 hash 值对 oldCap 取余不等于 0，说明这个节点是下标 0 之外的数组节点</span></span><br><span class="line">                        <span class="keyword">else</span> &#123;</span><br><span class="line">                            <span class="keyword">if</span> (hiTail == <span class="keyword">null</span>)</span><br><span class="line">                                hiHead = e;</span><br><span class="line">                            <span class="keyword">else</span></span><br><span class="line">                                hiTail.next = e;</span><br><span class="line">                            hiTail = e;</span><br><span class="line">                        &#125;</span><br><span class="line">                    &#125; <span class="keyword">while</span> ((e = next) != <span class="keyword">null</span>);</span><br><span class="line">                    <span class="comment">// 如果低位尾节点不为 null</span></span><br><span class="line">                    <span class="keyword">if</span> (loTail != <span class="keyword">null</span>) &#123;</span><br><span class="line">                        loTail.next = <span class="keyword">null</span>;</span><br><span class="line">                        <span class="comment">// 就把首节点赋值给新数组下标为 j 的桶，和旧数组的位置是一样的</span></span><br><span class="line">                        <span class="comment">// 也就是说节点原来对应在旧数组的哪个下标，在新数组也不变。</span></span><br><span class="line">                        <span class="comment">// 这里说点抽象的，把首节点赋值给新数组的桶，其实不单单只是首节点，因为每个节点都会有指针指向后继节点</span></span><br><span class="line">                        <span class="comment">// 所以其实可以想成是直接拉了一个链表到这个数组的某个桶里了。</span></span><br><span class="line">                        newTab[j] = loHead;</span><br><span class="line">                    &#125;</span><br><span class="line">                    <span class="keyword">if</span> (hiTail != <span class="keyword">null</span>) &#123;</span><br><span class="line">                        hiTail.next = <span class="keyword">null</span>;</span><br><span class="line">                        <span class="comment">// 就把首节点赋值给新数组下标为[j+oldCap]的桶，和旧数组的位置j相比，这里多偏移了旧数组长度oldCap个位置，变成了[j+oldCap]</span></span><br><span class="line">                        newTab[j + oldCap] = hiHead;</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> newTab;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>扩容过程中的几个关键的点：</p>
<ul>
<li>
<p>新初始化哈希表时，容量为默认容量 16，阈值为 容量*加载因子</p>
</li>
<li>
<p>第一种情况：已有哈希表扩容时，容量、阈值均为原来的 2 倍</p>
</li>
<li>
<p>第二种情况：如果之前这个桶的节点类型是树形节点，则需要把新哈希表里的当前桶也变成树形结构，调用 split() 做扩容</p>
</li>
<li>
<p>第三种情况：桶中已经形成链表，那么将原链表拆分成低位链表和高位链表，低位链表存放在扩容之后的原下标位置，高位链表存放在当前数组下标+扩容之前的数组长度</p>
<p>判断是属于低位链表还是高位链表的方法：<code>e.hash &amp; oldCap</code>，结果为 0 就是低位链表中的节点，结果为 1 就是高位链表中的节点</p>
</li>
</ul>
<blockquote>
<p>先略过红黑树的情况，描述下简单流程，在JDK1.8中发生 hashmap 扩容时，遍历 hashmap 每个桶里的链表，每个链表可能会被拆分成两个链表，不需要移动的元素置入 loHead 为首的链表，需要移动的元素置入 hiHead 为首的链表，然后分别分配给老的桶和新桶。</p>
</blockquote>
<p>JDK 1.8 没有再像之前一样再重新 rehash 了，效率自然是提高了很多。</p>
<h2 id="hashmap的获取方法get">HashMap的获取方法get()</h2>
<p><code>V get(K key)</code> 方法返回键对应的值</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> V <span class="title">get</span><span class="params">(Object key)</span> </span>&#123;</span><br><span class="line">    Node&lt;K,V&gt; e;</span><br><span class="line">    <span class="comment">// 先计算哈希值</span></span><br><span class="line">    <span class="keyword">return</span> (e = getNode(hash(key), key)) == <span class="keyword">null</span> ? <span class="keyword">null</span> : e.value;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">final</span> Node&lt;K,V&gt; <span class="title">getNode</span><span class="params">(<span class="keyword">int</span> hash, Object key)</span> </span>&#123;</span><br><span class="line">    Node&lt;K,V&gt;[] tab; Node&lt;K,V&gt; first, e; <span class="keyword">int</span> n; K k;</span><br><span class="line">    <span class="comment">// tab 指向哈希表，n 为哈希表的长度，first 指向哈希表的 [(n - 1) &amp; hash] 处桶的第一个元素</span></span><br><span class="line">    <span class="keyword">if</span> ((tab = table) != <span class="keyword">null</span> &amp;&amp; (n = tab.length) &gt; <span class="number">0</span> &amp;&amp;</span><br><span class="line">        (first = tab[(n - <span class="number">1</span>) &amp; hash]) != <span class="keyword">null</span>) &#123;</span><br><span class="line">        <span class="comment">// 检查第一个元素是否是我们要查找的元素</span></span><br><span class="line">        <span class="keyword">if</span> (first.hash == hash &amp;&amp; <span class="comment">// always check first node</span></span><br><span class="line">            ((k = first.key) == key || (key != <span class="keyword">null</span> &amp;&amp; key.equals(k))))</span><br><span class="line">            <span class="keyword">return</span> first;</span><br><span class="line">        <span class="comment">// 第一个元素不是我们要找的元素，且桶中还有其他元素</span></span><br><span class="line">        <span class="keyword">if</span> ((e = first.next) != <span class="keyword">null</span>) &#123;</span><br><span class="line">            <span class="comment">// 如果是桶中元素是树形节点，那么调用 getTreeNode() 函数进行查找</span></span><br><span class="line">            <span class="keyword">if</span> (first <span class="keyword">instanceof</span> TreeNode)</span><br><span class="line">                <span class="keyword">return</span> ((TreeNode&lt;K,V&gt;)first).getTreeNode(hash, key);</span><br><span class="line">            <span class="comment">// 遍历桶中元素进行查找</span></span><br><span class="line">            <span class="keyword">do</span> &#123;</span><br><span class="line">                <span class="keyword">if</span> (e.hash == hash &amp;&amp;</span><br><span class="line">                    ((k = e.key) == key || (key != <span class="keyword">null</span> &amp;&amp; key.equals(k))))</span><br><span class="line">                    <span class="keyword">return</span> e;</span><br><span class="line">            &#125; <span class="keyword">while</span> ((e = e.next) != <span class="keyword">null</span>);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>查找的步骤：</p>
<ul>
<li>计算哈希值</li>
<li>用 <code>(n - 1) &amp; hash</code> 计算出桶在哈希表中的位置</li>
<li>在桶中遍历进行查找</li>
</ul>
<p>时间复杂度一般跟桶中的元素多少有关，因此哈希算法越好，元素分布越均匀，get() 方法就越快。</p>
<p>但是在 JDK 1.8 之后 HashMap 新增了红黑树节点，优化了极端情况（所有元素都在一个桶中，一个链表中）下的性能。</p>
<h2 id="总结">总结</h2>
<ol>
<li>
<p>HashMap 的缺点是：不是同步的，多线程并发访问一个哈希表时需要在外部进行同步操作，否则会引发数据不同步问题，也可以选择加锁。</p>
</li>
<li>
<p>HashMap 的三个视图返回的迭代器都是 fail-fast 的：如果在迭代时使用了<strong>非迭代器方法</strong>修改了 map 的内容、结构，迭代器就会报 <code>ConcurrentModificationException</code> 的错。</p>
</li>
<li>
<p>当 HashMap 中由大量元素都存放到一个桶中时，这时哈希表中只有一个桶，这个通下边有一条很长的链表，此时的 HashMap 就相当于一个单链表。假设此时 HashMap 中有 n 个元素，遍历的时间复杂度就是 O(n)，完全失去了它的优势。</p>
<blockquote>
<p>针对这种情况，JDK 1.8 引入了红黑树（时间复杂度为)(logn)）来优化这个问题。</p>
</blockquote>
</li>
<li>
<p><span id="whyHashValue">为什么哈希表的容量一定要是 <strong>2 的整数次幂</strong>？</span></p>
<ol>
<li>capacity 为 2 的整数次幂，计算桶的位置 <code>(length - 1) &amp; hash</code> 就相当于 <code>hash</code> 对 <code>length</code> 取模，提升了计算效率；</li>
<li>capacity 为 2 的整数次幂的话，capacity 为偶数，<code>capacity - 1</code>  为奇数，奇数的最后一位是 1，那么 <code>(length - 1) &amp; hash</code> 的最后一位可能为 0 也可能为 1（这取决于 <code>hash</code> 的值），即按位与操作后的结果可能为偶数，也可能为奇数，这样便可以保证散列的均匀性；</li>
<li>如果 capacity 是奇数的话，<code>capacity - 1</code> 为偶数，它的最后一位是 0，这样 <code>(length - 1) &amp; hash</code> 的最后一位肯定是 0，即只能为偶数，这样任何 <code>hash</code> 值都只会被散列到数组的偶数下标位置上，这便浪费了近一半的空间。</li>
</ol>
</li>
<li>
<p>HashMap 允许 key、value 为 null，同时 key 为 null 的元素都保存在第一个桶中。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> <span class="title">hash</span><span class="params">(Object key)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> h;</span><br><span class="line">    <span class="keyword">return</span> (key == <span class="keyword">null</span>) ? <span class="number">0</span> : (h = key.hashCode()) ^ (h &gt;&gt;&gt; <span class="number">16</span>);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>计算哈希值时，如果为 null 就直接返回 0，说明了这一点。</p>
</li>
<li>
<p>HashMap 中 equals() 和 hashCode() 的作用：</p>
<ol>
<li>当 HashMap 进行添加、获取时需要通过 key 的 hashCode() 方法进行 hash() 操作，然后计算下下标 <code>(n - 1) &amp; hash)</code>，从而获得要找的桶的位置。</li>
<li>当发生冲突（碰撞）时，利用 key.equals() 方法去桶（链表或树）中查找对应的节点。</li>
</ol>
</li>
<li>
<p><span id="hashWhy">hash 为什么要这样实现？</span></p>
<p>在 JDK 1.8 的实现中，是通过hashCode() 的高16位异或低16位实现的：<code>(h = k.hashCode()) ^ (h &gt;&gt;&gt; 16)</code>。</p>
<p>主要是从<strong>速度、功效、质量</strong> 来考虑的，这么做可以在桶的 n 比较小的时候，保证高低 bit 都参与到 hash 的计算中，同时位运算不会有太大的开销。</p>
</li>
</ol>
<h1 id="hashmap在jdk18后新增的红黑树结构">HashMap在JDK1.8后新增的红黑树结构</h1>
<h2 id="传统hashmap的缺点">传统HashMap的缺点</h2>
<p>在 JDK 1.8 以前 HashMap 的实现是 数组+链表，即使哈希函数取得再好，也很难达到元素百分百的均匀分布。</p>
<p>当 HashMap 中有大量的元素都存放到同一个桶中时，这个桶下有一条长长的链表，这个时候 HashMap 就相当于一个单链表，假如单链表中有 n 个元素，遍历的时间复杂度就是 O(n)，完全失去了 HashMap 的优势。</p>
<p>针对这种情况，JDK 1.8 中引入了红黑树（查找时间复杂度为 O(logn)）来优化这个问题。</p>
<h2 id="红黑树">红黑树</h2>
<p>红黑树学习资料：</p>
<ul>
<li><a href="https://blog.csdn.net/u011240877/article/details/53329023" target="_blank" rel="noopener">重温数据结构：深入理解红黑树</a></li>
<li><a href="https://www.jianshu.com/p/e136ec79235c" target="_blank" rel="noopener">30张图带你彻底理解红黑树</a></li>
</ul>
<p>在 JDK 1.8 的 HashMap 中除了链表节点 <code>Node</code> 之外，还有一种节点：<code>TreeNode</code>，它是 JDK 1.8 新增的，属于数据结构中的红黑树。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">static</span> <span class="keyword">final</span> <span class="class"><span class="keyword">class</span> <span class="title">TreeNode</span>&lt;<span class="title">K</span>,<span class="title">V</span>&gt; <span class="keyword">extends</span> <span class="title">LinkedHashMap</span>.<span class="title">Entry</span>&lt;<span class="title">K</span>,<span class="title">V</span>&gt; </span>&#123;</span><br><span class="line">    TreeNode&lt;K,V&gt; parent;  <span class="comment">// red-black tree links</span></span><br><span class="line">    TreeNode&lt;K,V&gt; left;</span><br><span class="line">    TreeNode&lt;K,V&gt; right;</span><br><span class="line">    TreeNode&lt;K,V&gt; prev;    <span class="comment">// needed to unlink next upon deletion</span></span><br><span class="line">    <span class="keyword">boolean</span> red;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>它继承自 LinkedHashMap.Entry，而 LinkedHashMap.Entry 继承自 HashMap.Node，因此还有额外的 6 个属性：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 继承自linkedHashMap.Entry 的属性</span></span><br><span class="line">Entry&lt;K, V&gt; before, after;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 继承自HashMap.Node 的属性</span></span><br><span class="line"><span class="keyword">final</span> <span class="keyword">int</span> hash;</span><br><span class="line"><span class="keyword">final</span> K key;</span><br><span class="line">V value;</span><br><span class="line">Node&lt;K,V&gt; next;</span><br></pre></td></tr></table></figure>
<h2 id="hashmap中关于红黑树的三个关键参数">HashMap中关于红黑树的三个关键参数</h2>
<p>1、TREEIFY_THRESHOLD</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> TREEIFY_THRESHOLD = <span class="number">8</span>;</span><br></pre></td></tr></table></figure>
<p>一个桶的树化阈值，当桶中的元素超过这个值时，需要使用红黑树节点替换链表节点。这个值为 8，是从转换效率考虑的。</p>
<p>2、UNTREEIFY_THRESHOLD</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> UNTREEIFY_THRESHOLD = <span class="number">6</span>;</span><br></pre></td></tr></table></figure>
<p>一个树的链表还原阈值，当扩容时，桶中的元素个数小于这个值，就会把树形的桶元素还原（切分）为链表结构。这个值应该比树化阈值 TREEIFY_THRESHOLD 小，至少为 6，避免频繁转换。</p>
<p>3、MIN_TREEIFY_CAPACITY</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> MIN_TREEIFY_CAPACITY = <span class="number">64</span>;</span><br></pre></td></tr></table></figure>
<p>哈希表的最小树形化容量，当哈希表中的容量大于这个值时，表中的桶才能进行树形化，否则桶内元素大于树化阈值 TREEIFY_THRESHOLD 时会进行扩容，而不是树形化。为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD。</p>
<h2 id="桶的树形化操作treeifybin">桶的树形化操作treeifyBin()</h2>
<p>在Java 8 中，如果一个桶中的元素个数超过 TREEIFY_THRESHOLD（默认是 8），就使用红黑树来替换链表，从而提高速度。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">final</span> <span class="keyword">void</span> <span class="title">treeifyBin</span><span class="params">(Node&lt;K,V&gt;[] tab, <span class="keyword">int</span> hash)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> n, index; Node&lt;K,V&gt; e;</span><br><span class="line">    <span class="comment">// 如果当前哈希表为空，或者哈希表中元素的个数小于最小树形化容量(默认为 64)，就去新建/扩容</span></span><br><span class="line">    <span class="keyword">if</span> (tab == <span class="keyword">null</span> || (n = tab.length) &lt; MIN_TREEIFY_CAPACITY)</span><br><span class="line">        resize();</span><br><span class="line">    <span class="comment">// 如果哈希表中的元素超过了最小树形化容量，进行树形化</span></span><br><span class="line">    <span class="comment">// e 指向哈希表中指定桶中的第一个节点</span></span><br><span class="line">    <span class="keyword">else</span> <span class="keyword">if</span> ((e = tab[index = (n - <span class="number">1</span>) &amp; hash]) != <span class="keyword">null</span>) &#123;</span><br><span class="line">        TreeNode&lt;K,V&gt; hd = <span class="keyword">null</span>, tl = <span class="keyword">null</span>;</span><br><span class="line">        <span class="keyword">do</span> &#123;</span><br><span class="line">            <span class="comment">// 新建一个树形节点，内容和当前链表节点 e 一致</span></span><br><span class="line">            TreeNode&lt;K,V&gt; p = replacementTreeNode(e, <span class="keyword">null</span>);</span><br><span class="line">            <span class="comment">// 确定树头节点</span></span><br><span class="line">            <span class="keyword">if</span> (tl == <span class="keyword">null</span>)</span><br><span class="line">                hd = p;</span><br><span class="line">            <span class="keyword">else</span> &#123;</span><br><span class="line">                p.prev = tl;</span><br><span class="line">                tl.next = p;</span><br><span class="line">            &#125;</span><br><span class="line">            tl = p;</span><br><span class="line">        &#125; <span class="keyword">while</span> ((e = e.next) != <span class="keyword">null</span>);</span><br><span class="line">        <span class="comment">// 让桶的第一个元素指向新建的红黑树的头结点（根结点），以后这个桶里的元素就是红黑树而不是链表了</span></span><br><span class="line">        <span class="keyword">if</span> ((tab[index] = hd) != <span class="keyword">null</span>)</span><br><span class="line">            hd.treeify(tab);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// For treeifyBin</span></span><br><span class="line"><span class="function">TreeNode&lt;K,V&gt; <span class="title">replacementTreeNode</span><span class="params">(Node&lt;K,V&gt; p, Node&lt;K,V&gt; next)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">new</span> TreeNode&lt;&gt;(p.hash, p.key, p.value, next);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>上述操作做了：</p>
<ul>
<li>根据哈希表中元素个数，确定是扩容还是树形化</li>
<li>如果是树形化
<ul>
<li>遍历桶中的元素，创建相同个数的树形节点，复制内容，建立联系</li>
<li>然后让桶中第一个元素指向新建的树头节点（根节点），替换桶的链表内容为树形内容</li>
</ul>
</li>
</ul>
<p>但是我们发现，上述的操作并没有设置红黑树的颜色值，现在只能算得到了一个二叉树。在最后调用树形节点 <code>hd.treeify(tab)</code> 方法进行塑造红黑树。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">final</span> <span class="keyword">void</span> <span class="title">treeify</span><span class="params">(Node&lt;K,V&gt;[] tab)</span> </span>&#123;</span><br><span class="line">    TreeNode&lt;K,V&gt; root = <span class="keyword">null</span>;</span><br><span class="line">    <span class="comment">// x 指向红黑树的根节点（桶中第一个元素），因为是 hd.treeif(tab) 这样调用的</span></span><br><span class="line">    <span class="comment">// 第一层循环遍历当前桶中所有元素，将这些元素插入到红黑树当中</span></span><br><span class="line">    <span class="keyword">for</span> (TreeNode&lt;K,V&gt; x = <span class="keyword">this</span>, next; x != <span class="keyword">null</span>; x = next) &#123;</span><br><span class="line">        next = (TreeNode&lt;K,V&gt;)x.next;</span><br><span class="line">        x.left = x.right = <span class="keyword">null</span>;</span><br><span class="line">        <span class="comment">// 第一次进入循环，确定根节点，颜色为黑色</span></span><br><span class="line">        <span class="keyword">if</span> (root == <span class="keyword">null</span>) &#123;</span><br><span class="line">            x.parent = <span class="keyword">null</span>;</span><br><span class="line">            x.red = <span class="keyword">false</span>;</span><br><span class="line">            root = x;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">else</span> &#123;</span><br><span class="line">            K k = x.key;</span><br><span class="line">            <span class="keyword">int</span> h = x.hash;</span><br><span class="line">            Class&lt;?&gt; kc = <span class="keyword">null</span>;</span><br><span class="line">            <span class="comment">// 第二层循环遍历红黑树，确定当前 x 节点插入到红黑树中的位置</span></span><br><span class="line">            <span class="keyword">for</span> (TreeNode&lt;K,V&gt; p = root;;) &#123;</span><br><span class="line">                <span class="keyword">int</span> dir, ph;</span><br><span class="line">                K pk = p.key;</span><br><span class="line">                <span class="comment">// 确定 dir，dir 表示 x 应该处于当前节点的左子树还是右子树</span></span><br><span class="line">                <span class="keyword">if</span> ((ph = p.hash) &gt; h)</span><br><span class="line">                    dir = -<span class="number">1</span>;</span><br><span class="line">                <span class="keyword">else</span> <span class="keyword">if</span> (ph &lt; h)</span><br><span class="line">                    dir = <span class="number">1</span>;</span><br><span class="line">                <span class="comment">// 如果 hash 相等</span></span><br><span class="line">                <span class="keyword">else</span> <span class="keyword">if</span> ((kc == <span class="keyword">null</span> &amp;&amp;</span><br><span class="line">                          <span class="comment">// 如果没实现 Comparable 接口，通过特殊的方法给个结果</span></span><br><span class="line">                          (kc = comparableClassFor(k)) == <span class="keyword">null</span>) ||</span><br><span class="line">                         <span class="comment">// 如果实现了 Comparable 接口，那么用 Comparable 接口比较键 key</span></span><br><span class="line">                         (dir = compareComparables(kc, k, pk)) == <span class="number">0</span>)</span><br><span class="line">                    <span class="comment">// 虽然 hash 相等，但是键没有实现 Comparable 接口无法比较，所以只能用特殊的方法给个结果</span></span><br><span class="line">                    dir = tieBreakOrder(k, pk);</span><br><span class="line"></span><br><span class="line">                TreeNode&lt;K,V&gt; xp = p;</span><br><span class="line">                <span class="comment">// 如果 p 的左子树或者右子树为空，则把 p 节点当作是 x 节点的父亲节点</span></span><br><span class="line">                <span class="comment">// 并根据 dir 的大小确定 x 节点为 p 节点的左子树还是右子树</span></span><br><span class="line">                <span class="keyword">if</span> ((p = (dir &lt;= <span class="number">0</span>) ? p.left : p.right) == <span class="keyword">null</span>) &#123;</span><br><span class="line">                    x.parent = xp;</span><br><span class="line">                    <span class="keyword">if</span> (dir &lt;= <span class="number">0</span>)</span><br><span class="line">                        xp.left = x;</span><br><span class="line">                    <span class="keyword">else</span></span><br><span class="line">                        xp.right = x;</span><br><span class="line">                    <span class="comment">// 平衡红黑树</span></span><br><span class="line">                    root = balanceInsertion(root, x);</span><br><span class="line">                    <span class="keyword">break</span>;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 确保 root 节点是桶中的第一个节点</span></span><br><span class="line">    moveRootToFront(tab, root);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//这个方法用于 a 和 b 哈希值相同但是无法比较时，直接根据两个引用的地址进行比较</span></span><br><span class="line"><span class="comment">//这里源码注释也说了，这个树里不要求完全有序，只要插入时使用相同的规则保持平衡即可</span></span><br><span class="line"><span class="function"><span class="keyword">static</span> <span class="keyword">int</span> <span class="title">tieBreakOrder</span><span class="params">(Object a, Object b)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> d;</span><br><span class="line">    <span class="keyword">if</span> (a == <span class="keyword">null</span> || b == <span class="keyword">null</span> ||</span><br><span class="line">        (d = a.getClass().getName().</span><br><span class="line">         compareTo(b.getClass().getName())) == <span class="number">0</span>)</span><br><span class="line">        d = (System.identityHashCode(a) &lt;= System.identityHashCode(b) ?</span><br><span class="line">             -<span class="number">1</span> : <span class="number">1</span>);</span><br><span class="line">    <span class="keyword">return</span> d;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>这里有个双重循环，拿树中的所有节点和当前节点的哈希值进行对比(如果哈希值相等，就对比键），然后根据比较结果确定在树中的位置。</p>
<p><strong>总结 treeifyBin() 的操作：</strong></p>
<ul>
<li>根据哈希表中元素个数，确定是扩容还是树形化</li>
<li>如果是树形化
<ul>
<li>遍历桶中的元素，创建相同个数的树形节点，复制内容，建立联系（确定前后关系）</li>
<li>让桶中第一个元素指向新建的树头节点（根节点），替换桶的链表内容为树形内容</li>
<li>调用 <code>treeify()</code> 函数，遍历桶中所有元素，依次插入，塑造红黑树</li>
</ul>
</li>
</ul>
<h2 id="红黑树中添加元素puttreeval">红黑树中添加元素putTreeVal()</h2>
<p>在添加元素时，如果一个桶已经是红黑树结构，就要调用 putTreeVal() 方法。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">final</span> TreeNode&lt;K,V&gt; <span class="title">putTreeVal</span><span class="params">(HashMap&lt;K,V&gt; map, Node&lt;K,V&gt;[] tab,</span></span></span><br><span class="line"><span class="function"><span class="params">                               <span class="keyword">int</span> h, K k, V v)</span> </span>&#123;</span><br><span class="line">    Class&lt;?&gt; kc = <span class="keyword">null</span>;</span><br><span class="line">    <span class="keyword">boolean</span> searched = <span class="keyword">false</span>;</span><br><span class="line">    TreeNode&lt;K,V&gt; root = (parent != <span class="keyword">null</span>) ? root() : <span class="keyword">this</span>;</span><br><span class="line">    <span class="comment">// 寻找插入的位置</span></span><br><span class="line">    <span class="keyword">for</span> (TreeNode&lt;K,V&gt; p = root;;) &#123;</span><br><span class="line">        <span class="keyword">int</span> dir, ph; K pk;</span><br><span class="line">        <span class="comment">// 根据 hash 判断插入的位置在当前节点的左边还是右边</span></span><br><span class="line">        <span class="keyword">if</span> ((ph = p.hash) &gt; h)</span><br><span class="line">            dir = -<span class="number">1</span>;</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> (ph &lt; h)</span><br><span class="line">            dir = <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> ((pk = p.key) == k || (k != <span class="keyword">null</span> &amp;&amp; k.equals(pk)))</span><br><span class="line">            <span class="keyword">return</span> p;</span><br><span class="line">        <span class="comment">// 如果当前节点 p 和节点 x 的 hash 相等，但键却不是同一个类</span></span><br><span class="line">        <span class="comment">// 在 p 的左右子树中去寻找</span></span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> ((kc == <span class="keyword">null</span> &amp;&amp;</span><br><span class="line">                  <span class="comment">// 如果没实现 Comparable 接口，通过特殊的方法给个结果</span></span><br><span class="line">                  (kc = comparableClassFor(k)) == <span class="keyword">null</span>) ||</span><br><span class="line">                 <span class="comment">// 如果实现了 Comparable 接口，那么用 Comparable 接口比较键 key</span></span><br><span class="line">                 (dir = compareComparables(kc, k, pk)) == <span class="number">0</span>) &#123;</span><br><span class="line">            <span class="keyword">if</span> (!searched) &#123;</span><br><span class="line">                TreeNode&lt;K,V&gt; q, ch;</span><br><span class="line">                searched = <span class="keyword">true</span>;</span><br><span class="line">                <span class="keyword">if</span> (((ch = p.left) != <span class="keyword">null</span> &amp;&amp;</span><br><span class="line">                     (q = ch.find(h, k, kc)) != <span class="keyword">null</span>) ||</span><br><span class="line">                    ((ch = p.right) != <span class="keyword">null</span> &amp;&amp;</span><br><span class="line">                     (q = ch.find(h, k, kc)) != <span class="keyword">null</span>))</span><br><span class="line">                    <span class="comment">//如果从 ch 所在子树中可以找到要添加的节点，就直接返回</span></span><br><span class="line">                    <span class="keyword">return</span> q;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="comment">// 走到这里就说明，遍历了所有子节点也没有找到和当前键equals相等的节点，必须进行插入操作</span></span><br><span class="line">            <span class="comment">// 虽然 hash 相等，但是键没有实现 Comparable 接口无法比较，所以只能用特殊的方法给个结果</span></span><br><span class="line">            dir = tieBreakOrder(k, pk);</span><br><span class="line">        &#125;</span><br><span class="line">		</span><br><span class="line">        TreeNode&lt;K,V&gt; xp = p;</span><br><span class="line">        <span class="comment">// 如果恰好要添加的方向上的子节点为空，此时节点p已经指向了这个空的子节点</span></span><br><span class="line">        <span class="keyword">if</span> ((p = (dir &lt;= <span class="number">0</span>) ? p.left : p.right) == <span class="keyword">null</span>) &#123;</span><br><span class="line">            Node&lt;K,V&gt; xpn = xp.next;</span><br><span class="line">            TreeNode&lt;K,V&gt; x = map.newTreeNode(h, k, v, xpn);</span><br><span class="line">            <span class="keyword">if</span> (dir &lt;= <span class="number">0</span>)</span><br><span class="line">                xp.left = x;</span><br><span class="line">            <span class="keyword">else</span></span><br><span class="line">                xp.right = x;</span><br><span class="line">            xp.next = x;</span><br><span class="line">            x.parent = x.prev = xp;</span><br><span class="line">            <span class="keyword">if</span> (xpn != <span class="keyword">null</span>)</span><br><span class="line">                ((TreeNode&lt;K,V&gt;)xpn).prev = x;</span><br><span class="line">            <span class="comment">// 平衡红黑树，且确保根节点是桶中的第一个元素</span></span><br><span class="line">            moveRootToFront(tab, balanceInsertion(root, x));</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//这个方法用于 a 和 b 哈希值相同但是无法比较时，直接根据两个引用的地址进行比较</span></span><br><span class="line"><span class="comment">//这里源码注释也说了，这个树里不要求完全有序，只要插入时使用相同的规则保持平衡即可</span></span><br><span class="line"><span class="function"><span class="keyword">static</span> <span class="keyword">int</span> <span class="title">tieBreakOrder</span><span class="params">(Object a, Object b)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> d;</span><br><span class="line">    <span class="keyword">if</span> (a == <span class="keyword">null</span> || b == <span class="keyword">null</span> ||</span><br><span class="line">        (d = a.getClass().getName().</span><br><span class="line">         compareTo(b.getClass().getName())) == <span class="number">0</span>)</span><br><span class="line">        d = (System.identityHashCode(a) &lt;= System.identityHashCode(b) ?</span><br><span class="line">             -<span class="number">1</span> : <span class="number">1</span>);</span><br><span class="line">    <span class="keyword">return</span> d;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>通过上面的代码知道，HashMap 中往红黑树添加一个新的节点时有以下操作：</p>
<ul>
<li>
<p>从红黑树的根节点开始寻找，如果目标键的哈希值小于当前节点键的哈希值，那么到左子树寻找；如果大于当前节点键的哈希值，到右子树寻找；如果找到键的哈希值相同且键 equals 相等的节点 p，那么直接返回节点 p。</p>
</li>
<li>
<p>如果键的哈希值相同，但是键并不是 equals 相等，进而通过 Comparable 接口进行比较，如果比较的结果还是相等，则在左右子树递归的寻找是否有与要插入的元素的 key equals 相等的元素。如果有那么直接返回，如果没有就只能通过特殊的方法给个结果。</p>
<p>（也就是说，没有实现 Comparable 接口，大小由 tieBreakOrder() 函数判定，如果实现了，则由 Comparable 接口的比较方法判定）</p>
</li>
<li>
<p>如果遍历完所有的节点都没有找到哈希值和键 equals 相等的节点，就需要插入该新节点。</p>
</li>
<li>
<p>插入完成后，需要重新平衡红黑树，且确保根节点是桶中的第一个元素。</p>
</li>
</ul>
<h2 id="红黑树中查找元素gettreenode">红黑树中查找元素getTreeNode()</h2>
<p>HashMap 的查找方法是 get()，它通过计算指定 key 的哈希值后，调用内部方法 getNode()，该方法根据 <code>(n-1) &amp; hash</code> 得到 key 所在的桶的头结点，判断头结点是否为所要查找的元素，如果不是且桶中节点类型是红黑树节点，就需要调用红黑树节点的 getTreeNode() 方法，否则就遍历链表中的节点。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">final</span> TreeNode&lt;K,V&gt; <span class="title">getTreeNode</span><span class="params">(<span class="keyword">int</span> h, Object k)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">return</span> ((parent != <span class="keyword">null</span>) ? root() : <span class="keyword">this</span>).find(h, k, <span class="keyword">null</span>);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>getTreeNode() 方法通过调用树形节点的 find() 方法进行查找：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">final</span> TreeNode&lt;K,V&gt; <span class="title">find</span><span class="params">(<span class="keyword">int</span> h, Object k, Class&lt;?&gt; kc)</span> </span>&#123;</span><br><span class="line">    TreeNode&lt;K,V&gt; p = <span class="keyword">this</span>;</span><br><span class="line">    <span class="keyword">do</span> &#123;</span><br><span class="line">        <span class="keyword">int</span> ph, dir; K pk;</span><br><span class="line">        TreeNode&lt;K,V&gt; pl = p.left, pr = p.right, q;</span><br><span class="line">        <span class="keyword">if</span> ((ph = p.hash) &gt; h)</span><br><span class="line">            p = pl;</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> (ph &lt; h)</span><br><span class="line">            p = pr;</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> ((pk = p.key) == k || (k != <span class="keyword">null</span> &amp;&amp; k.equals(pk)))</span><br><span class="line">            <span class="keyword">return</span> p;</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> (pl == <span class="keyword">null</span>)</span><br><span class="line">            p = pr;</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> (pr == <span class="keyword">null</span>)</span><br><span class="line">            p = pl;</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> ((kc != <span class="keyword">null</span> ||</span><br><span class="line">                  (kc = comparableClassFor(k)) != <span class="keyword">null</span>) &amp;&amp;</span><br><span class="line">                 (dir = compareComparables(kc, k, pk)) != <span class="number">0</span>)</span><br><span class="line">            p = (dir &lt; <span class="number">0</span>) ? pl : pr;</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> ((q = pr.find(h, k, kc)) != <span class="keyword">null</span>)</span><br><span class="line">            <span class="keyword">return</span> q;</span><br><span class="line">        <span class="keyword">else</span></span><br><span class="line">            p = pl;</span><br><span class="line">    &#125; <span class="keyword">while</span> (p != <span class="keyword">null</span>);</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>由于之前添加时已经保证这个红黑树是有序的，因此查找时效率很高（相当于折半查找）。</p>
<h2 id="树形结构修剪split">树形结构修剪split()</h2>
<p>在 HashMap 中，resize() 方法的作用是初始化或者扩容哈希表。当扩容时，如果当前桶中元素的结构是红黑树，并且元素个数小于链表还原阈值 UNTREEIFY_THRESHOLD（默认为 6），就会把桶中的树形结构缩小或者直接还原（切分）为链表，调用的就是 split()：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// ((TreeNode&lt;K,V&gt;)e).split(this, newTab, j, oldCap);</span></span><br><span class="line"><span class="comment">// 将树形结构拆分为两个小红黑树，如果太小就还原成链表</span></span><br><span class="line"><span class="comment">// map：当前hashMap对象、tab：新数组、index：正在遍历的旧数组下标、bit：旧数组的长度</span></span><br><span class="line"><span class="function"><span class="keyword">final</span> <span class="keyword">void</span> <span class="title">split</span><span class="params">(HashMap&lt;K,V&gt; map, Node&lt;K,V&gt;[] tab, <span class="keyword">int</span> index, <span class="keyword">int</span> bit)</span> </span>&#123;</span><br><span class="line">    TreeNode&lt;K,V&gt; b = <span class="keyword">this</span>;</span><br><span class="line">    <span class="comment">// Relink into lo and hi lists, preserving order</span></span><br><span class="line">    TreeNode&lt;K,V&gt; loHead = <span class="keyword">null</span>, loTail = <span class="keyword">null</span>;</span><br><span class="line">    TreeNode&lt;K,V&gt; hiHead = <span class="keyword">null</span>, hiTail = <span class="keyword">null</span>;</span><br><span class="line">    <span class="keyword">int</span> lc = <span class="number">0</span>, hc = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (TreeNode&lt;K,V&gt; e = b, next; e != <span class="keyword">null</span>; e = next) &#123;</span><br><span class="line">        next = (TreeNode&lt;K,V&gt;)e.next;</span><br><span class="line">        e.next = <span class="keyword">null</span>;</span><br><span class="line">        <span class="comment">// 区分树链表的高低位</span></span><br><span class="line">        <span class="keyword">if</span> ((e.hash &amp; bit) == <span class="number">0</span>) &#123;</span><br><span class="line">            <span class="comment">// 低位尾部标记为 null，表示还未开始处理</span></span><br><span class="line">            <span class="comment">// 此时 e 是第一个要处理的低位树链表节点</span></span><br><span class="line">            <span class="keyword">if</span> ((e.prev = loTail) == <span class="keyword">null</span>)</span><br><span class="line">                <span class="comment">// 低位树链表的第一个树链表节点</span></span><br><span class="line">                loHead = e;</span><br><span class="line">            <span class="keyword">else</span></span><br><span class="line">                loTail.next = e;</span><br><span class="line">            loTail = e;</span><br><span class="line">			<span class="comment">// 低位树链表元素个数计数</span></span><br><span class="line">            ++lc;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">else</span> &#123;</span><br><span class="line">            <span class="keyword">if</span> ((e.prev = hiTail) == <span class="keyword">null</span>)</span><br><span class="line">				<span class="comment">// 高位树链表的第一个树链表节点</span></span><br><span class="line">                hiHead = e;</span><br><span class="line">            <span class="keyword">else</span></span><br><span class="line">                hiTail.next = e;</span><br><span class="line">            hiTail = e;</span><br><span class="line">            <span class="comment">// 高位树链表元素个数计数</span></span><br><span class="line">            ++hc;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">	<span class="comment">// 如果低位树链表头节点不为 null，说明链表存在</span></span><br><span class="line">    <span class="keyword">if</span> (loHead != <span class="keyword">null</span>) &#123;</span><br><span class="line">        <span class="comment">// 如果低位树链表中的元素小于等于链表还原阈值 6</span></span><br><span class="line">        <span class="keyword">if</span> (lc &lt;= UNTREEIFY_THRESHOLD)</span><br><span class="line">            <span class="comment">// 去树化操作（将 TreeNode 节点都转换成 Node 节点）</span></span><br><span class="line">            tab[index] = loHead.untreeify(map);</span><br><span class="line">        <span class="keyword">else</span> &#123;</span><br><span class="line">            tab[index] = loHead;</span><br><span class="line">            <span class="comment">// 若高位树链表头节点不为空，说明还没有处理完高位，还不能进行树形化操作</span></span><br><span class="line">            <span class="keyword">if</span> (hiHead != <span class="keyword">null</span>) <span class="comment">// (else is already treeified)</span></span><br><span class="line">                <span class="comment">// 低位树链表的元素个数大于 6 且高位树链表的头节点不为 null</span></span><br><span class="line">                <span class="comment">// 将低位树链表真正树化成红黑树（前面都只是挂着 TreeNode 的名号，但实际只是链表结构，还没包含红黑树的特性，这里才赋予了它红黑树的特性）</span></span><br><span class="line">                loHead.treeify(tab);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 高位树链表不为 null，同上</span></span><br><span class="line">    <span class="keyword">if</span> (hiHead != <span class="keyword">null</span>) &#123;</span><br><span class="line">        <span class="keyword">if</span> (hc &lt;= UNTREEIFY_THRESHOLD)</span><br><span class="line">            tab[index + bit] = hiHead.untreeify(map);</span><br><span class="line">        <span class="keyword">else</span> &#123;</span><br><span class="line">            tab[index + bit] = hiHead;</span><br><span class="line">            <span class="keyword">if</span> (loHead != <span class="keyword">null</span>)</span><br><span class="line">                hiHead.treeify(tab);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>从上述代码可以看到，HashMap 扩容时对红黑树节点的修建主要分两部分，先分类，再根据元素个数决定是还原成链表还是精简一下元素仍然保留红黑树结构。</p>
<ol>
<li>
<p>分类</p>
<p>指定位置、指定范围，让指定位置中 <code>(hash &amp; bit) == 0</code> 的放到低位树链表中，<code>(hash &amp; bit) == 1</code> 的放到高位树链表中。</p>
</li>
<li>
<p>根据元素个数决定处理情况</p>
<p>树链表中的元素个数小于树的链表还原阈值 6 时，将树还原成链表；在元素个数大于 6 时，还是用红黑树。</p>
<p>其中低位树链表存放在当前桶所在的下标，高位树链表存放在当前桶所在的下标 + 扩容之前的数组长度。</p>
</li>
</ol>
<h2 id="总结">总结</h2>
<p>JDK 1.8 以后哈希表的添加、删除、查找、扩容方法都增加了一种 <code>节点为 TreeNode</code> 的情况：</p>
<ul>
<li>添加时，当桶中链表个数超过 8 且哈希表中的元素超过了最小树形化容量时，会被转换成红黑树；</li>
<li>删除、扩容时，如果桶中结构为红黑树，并且树中元素个数小于 6 时，会进行去树化操作，还原成链表；</li>
<li>查找时即使哈希函数不优，大量元素集中在一个桶中，由于有红黑树结构，性能也不会差。</li>
</ul>
<p><img src="https://pic.tyzhang.top/images/2021/01/08/image.png" alt="image.png"></p>

                
                <hr>
                <!-- Pager -->
                <ul class="pager">
                    
                        <li class="previous">
                            <a href="/article/Python修改文件名/" data-toggle="tooltip" data-placement="top" title="Python批量处理文件名">&larr; 上一篇</a>
                        </li>
                    
                    
                        <li class="next">
                            <a href="/article/Java中的移位运算符/" data-toggle="tooltip" data-placement="top" title="Java中的移位运算符：<<,>>,>>> ">下一篇 &rarr;</a>
                        </li>
                    
                </ul>

                <br>

                <!--打赏-->
                
                <!--打赏-->

                <br>
                <!--分享-->
                
                <!--分享-->
                <br>                       
                
                <!-- require APlayer -->
                
            </div>
            
            <!-- Tabe of Content -->
            <!-- Table of Contents -->

  
    <style>
      span.toc-nav-number{
        display: none
      }
    </style>
  
    
      <aside id="sidebar">
        <div id="toc" class="toc-article">
        <strong class="toc-title">目录</strong>
        
          <ol class="toc-nav"><li class="toc-nav-item toc-nav-level-1"><a class="toc-nav-link" href="#iterator迭代器"><span class="toc-nav-number">1.</span> <span class="toc-nav-text">Iterator&#x8FED;&#x4EE3;&#x5668;</span></a><ol class="toc-nav-child"><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#concurrentmodificationexception-出现的原因fail-fast"><span class="toc-nav-number">1.1.</span> <span class="toc-nav-text">ConcurrentModificationException &#x51FA;&#x73B0;&#x7684;&#x539F;&#x56E0;&#xFF08;fail-fast&#xFF09;</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#api"><span class="toc-nav-number">1.2.</span> <span class="toc-nav-text">API</span></a></li></ol></li><li class="toc-nav-item toc-nav-level-1"><a class="toc-nav-link" href="#listiterator双向迭代器"><span class="toc-nav-number">2.</span> <span class="toc-nav-text">ListIterator&#x53CC;&#x5411;&#x8FED;&#x4EE3;&#x5668;</span></a><ol class="toc-nav-child"><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#listiterator的获取"><span class="toc-nav-number">2.1.</span> <span class="toc-nav-text">ListIterator&#x7684;&#x83B7;&#x53D6;</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#api"><span class="toc-nav-number">2.2.</span> <span class="toc-nav-text">API</span></a></li></ol></li><li class="toc-nav-item toc-nav-level-1"><a class="toc-nav-link" href="#collection集合"><span class="toc-nav-number">3.</span> <span class="toc-nav-text">Collection&#x96C6;&#x5408;</span></a><ol class="toc-nav-child"><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#集合的概念"><span class="toc-nav-number">3.1.</span> <span class="toc-nav-text">&#x96C6;&#x5408;&#x7684;&#x6982;&#x5FF5;</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#集合框架"><span class="toc-nav-number">3.2.</span> <span class="toc-nav-text">&#x96C6;&#x5408;&#x6846;&#x67B6;</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#java集合框架主要结构图"><span class="toc-nav-number">3.3.</span> <span class="toc-nav-text">Java&#x96C6;&#x5408;&#x6846;&#x67B6;&#x4E3B;&#x8981;&#x7ED3;&#x6784;&#x56FE;</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#15个核心api"><span class="toc-nav-number">3.4.</span> <span class="toc-nav-text">15&#x4E2A;&#x6838;&#x5FC3;API</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#遍历collection的方法"><span class="toc-nav-number">3.5.</span> <span class="toc-nav-text">&#x904D;&#x5386;Collection&#x7684;&#x65B9;&#x6CD5;</span></a><ol class="toc-nav-child"><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#1-for-each语法"><span class="toc-nav-number">3.5.1.</span> <span class="toc-nav-text">1&#x3001;for-each&#x8BED;&#x6CD5;</span></a></li><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#2-iterator迭代器"><span class="toc-nav-number">3.5.2.</span> <span class="toc-nav-text">2&#x3001;Iterator&#x8FED;&#x4EE3;&#x5668;</span></a></li></ol></li></ol></li><li class="toc-nav-item toc-nav-level-1"><a class="toc-nav-link" href="#listltegt接口"><span class="toc-nav-number">4.</span> <span class="toc-nav-text">List&lt;E&gt;&#x63A5;&#x53E3;</span></a><ol class="toc-nav-child"><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#list接口扩展的方法"><span class="toc-nav-number">4.1.</span> <span class="toc-nav-text">List&#x63A5;&#x53E3;&#x6269;&#x5C55;&#x7684;&#x65B9;&#x6CD5;</span></a></li></ol></li><li class="toc-nav-item toc-nav-level-1"><a class="toc-nav-link" href="#abstractcollection抽象类"><span class="toc-nav-number">5.</span> <span class="toc-nav-text">AbstractCollection&#x62BD;&#x8C61;&#x7C7B;</span></a></li><li class="toc-nav-item toc-nav-level-1"><a class="toc-nav-link" href="#arraylist类"><span class="toc-nav-number">6.</span> <span class="toc-nav-text">ArrayList&#x7C7B;</span></a><ol class="toc-nav-child"><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#arraylist的成员变量"><span class="toc-nav-number">6.1.</span> <span class="toc-nav-text">ArrayList&#x7684;&#x6210;&#x5458;&#x53D8;&#x91CF;</span></a><ol class="toc-nav-child"><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#1-底层数据结构数组"><span class="toc-nav-number">6.1.1.</span> <span class="toc-nav-text">1&#x3001;&#x5E95;&#x5C42;&#x6570;&#x636E;&#x7ED3;&#x6784;&#xFF1A;&#x6570;&#x7EC4;</span></a></li><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#2-默认的空数组"><span class="toc-nav-number">6.1.2.</span> <span class="toc-nav-text"><span id="emptyArray">2&#x3001;&#x9ED8;&#x8BA4;&#x7684;&#x7A7A;&#x6570;&#x7EC4;</span></span></a></li><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#3-数组的初始容量为10"><span class="toc-nav-number">6.1.3.</span> <span class="toc-nav-text">3&#x3001;&#x6570;&#x7EC4;&#x7684;&#x521D;&#x59CB;&#x5BB9;&#x91CF;&#x4E3A;10</span></a></li><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#4-数组中当前元素个数"><span class="toc-nav-number">6.1.4.</span> <span class="toc-nav-text">4&#x3001;&#x6570;&#x7EC4;&#x4E2D;&#x5F53;&#x524D;&#x5143;&#x7D20;&#x4E2A;&#x6570;</span></a></li><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#5-数组最大容量"><span class="toc-nav-number">6.1.5.</span> <span class="toc-nav-text">5&#x3001;&#x6570;&#x7EC4;&#x6700;&#x5927;&#x5BB9;&#x91CF;</span></a></li></ol></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#arraylist的关键方法"><span class="toc-nav-number">6.2.</span> <span class="toc-nav-text">ArrayList&#x7684;&#x5173;&#x952E;&#x65B9;&#x6CD5;</span></a><ol class="toc-nav-child"><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#1-构造函数"><span class="toc-nav-number">6.2.1.</span> <span class="toc-nav-text">1&#x3001;&#x6784;&#x9020;&#x51FD;&#x6570;</span></a></li><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#2-添加元素"><span class="toc-nav-number">6.2.2.</span> <span class="toc-nav-text">2&#x3001;&#x6DFB;&#x52A0;&#x5143;&#x7D20;</span></a></li><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#3-对数组容量进行调整"><span class="toc-nav-number">6.2.3.</span> <span class="toc-nav-text">3&#x3001;&#x5BF9;&#x6570;&#x7EC4;&#x5BB9;&#x91CF;&#x8FDB;&#x884C;&#x8C03;&#x6574;</span></a></li><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#4-扩容"><span class="toc-nav-number">6.2.4.</span> <span class="toc-nav-text">4&#x3001;&#x6269;&#x5BB9;</span></a></li></ol></li></ol></li><li class="toc-nav-item toc-nav-level-1"><a class="toc-nav-link" href="#queue接口队列"><span class="toc-nav-number">7.</span> <span class="toc-nav-text">Queue&#x63A5;&#x53E3;&#xFF0C;&#x961F;&#x5217;</span></a><ol class="toc-nav-child"><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#额外添加的api"><span class="toc-nav-number">7.1.</span> <span class="toc-nav-text">&#x989D;&#x5916;&#x6DFB;&#x52A0;&#x7684;API</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#为什么建议禁止添加-null-元素"><span class="toc-nav-number">7.2.</span> <span class="toc-nav-text">&#x4E3A;&#x4EC0;&#x4E48;&#x5EFA;&#x8BAE;&#x7981;&#x6B62;&#x6DFB;&#x52A0; null &#x5143;&#x7D20;</span></a></li></ol></li><li class="toc-nav-item toc-nav-level-1"><a class="toc-nav-link" href="#deque接口双端队列"><span class="toc-nav-number">8.</span> <span class="toc-nav-text">Deque&#x63A5;&#x53E3;&#xFF0C;&#x53CC;&#x7AEF;&#x961F;&#x5217;</span></a><ol class="toc-nav-child"><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#deque-的实现类"><span class="toc-nav-number">8.1.</span> <span class="toc-nav-text">Deque &#x7684;&#x5B9E;&#x73B0;&#x7C7B;</span></a></li></ol></li><li class="toc-nav-item toc-nav-level-1"><a class="toc-nav-link" href="#linkedlist类"><span class="toc-nav-number">9.</span> <span class="toc-nav-text">LinkedList&#x7C7B;</span></a><ol class="toc-nav-child"><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#linkedlist双向链表实现"><span class="toc-nav-number">9.1.</span> <span class="toc-nav-text">LinkedList&#x53CC;&#x5411;&#x94FE;&#x8868;&#x5B9E;&#x73B0;</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#linkedlist的方法"><span class="toc-nav-number">9.2.</span> <span class="toc-nav-text">LinkedList&#x7684;&#x65B9;&#x6CD5;</span></a><ol class="toc-nav-child"><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#1-关键的几个内部方法"><span class="toc-nav-number">9.2.1.</span> <span class="toc-nav-text">1&#x3001;&#x5173;&#x952E;&#x7684;&#x51E0;&#x4E2A;&#x5185;&#x90E8;&#x65B9;&#x6CD5;</span></a></li><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#2-常用的-api"><span class="toc-nav-number">9.2.2.</span> <span class="toc-nav-text">2&#x3001;&#x5E38;&#x7528;&#x7684; API</span></a><ol class="toc-nav-child"><li class="toc-nav-item toc-nav-level-4"><a class="toc-nav-link" href="#添加方法"><span class="toc-nav-number">9.2.2.1.</span> <span class="toc-nav-text">&#x6DFB;&#x52A0;&#x65B9;&#x6CD5;</span></a></li><li class="toc-nav-item toc-nav-level-4"><a class="toc-nav-link" href="#删除方法"><span class="toc-nav-number">9.2.2.2.</span> <span class="toc-nav-text">&#x5220;&#x9664;&#x65B9;&#x6CD5;</span></a></li><li class="toc-nav-item toc-nav-level-4"><a class="toc-nav-link" href="#修改方法"><span class="toc-nav-number">9.2.2.3.</span> <span class="toc-nav-text">&#x4FEE;&#x6539;&#x65B9;&#x6CD5;</span></a></li><li class="toc-nav-item toc-nav-level-4"><a class="toc-nav-link" href="#查询方法"><span class="toc-nav-number">9.2.2.4.</span> <span class="toc-nav-text">&#x67E5;&#x8BE2;&#x65B9;&#x6CD5;</span></a></li></ol></li></ol></li></ol></li><li class="toc-nav-item toc-nav-level-1"><a class="toc-nav-link" href="#arraylist和linkedlist的比较"><span class="toc-nav-number">10.</span> <span class="toc-nav-text">ArrayList&#x548C;LinkedList&#x7684;&#x6BD4;&#x8F83;</span></a></li><li class="toc-nav-item toc-nav-level-1"><a class="toc-nav-link" href="#vector类"><span class="toc-nav-number">11.</span> <span class="toc-nav-text">Vector&#x7C7B;</span></a><ol class="toc-nav-child"><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#成员变量"><span class="toc-nav-number">11.1.</span> <span class="toc-nav-text">&#x6210;&#x5458;&#x53D8;&#x91CF;</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#vector特点"><span class="toc-nav-number">11.2.</span> <span class="toc-nav-text">Vector&#x7279;&#x70B9;</span></a></li></ol></li><li class="toc-nav-item toc-nav-level-1"><a class="toc-nav-link" href="#vector和arraylist的比较"><span class="toc-nav-number">12.</span> <span class="toc-nav-text">Vector&#x548C;ArrayList&#x7684;&#x6BD4;&#x8F83;</span></a></li><li class="toc-nav-item toc-nav-level-1"><a class="toc-nav-link" href="#stack栈"><span class="toc-nav-number">13.</span> <span class="toc-nav-text">Stack&#x6808;</span></a><ol class="toc-nav-child"><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#stack的方法"><span class="toc-nav-number">13.1.</span> <span class="toc-nav-text">Stack&#x7684;&#x65B9;&#x6CD5;</span></a></li></ol></li><li class="toc-nav-item toc-nav-level-1"><a class="toc-nav-link" href="#map接口"><span class="toc-nav-number">14.</span> <span class="toc-nav-text">Map&#x63A5;&#x53E3;</span></a><ol class="toc-nav-child"><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#视图"><span class="toc-nav-number">14.1.</span> <span class="toc-nav-text">&#x89C6;&#x56FE;</span></a><ol class="toc-nav-child"><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#keyset"><span class="toc-nav-number">14.1.1.</span> <span class="toc-nav-text">KeySet</span></a></li><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#values"><span class="toc-nav-number">14.1.2.</span> <span class="toc-nav-text">Values</span></a></li><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#entry"><span class="toc-nav-number">14.1.3.</span> <span class="toc-nav-text">Entry</span></a></li></ol></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#map的三种遍历方式"><span class="toc-nav-number">14.2.</span> <span class="toc-nav-text">Map&#x7684;&#x4E09;&#x79CD;&#x904D;&#x5386;&#x65B9;&#x5F0F;</span></a><ol class="toc-nav-child"><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#1-使用-keyset-遍历"><span class="toc-nav-number">14.2.1.</span> <span class="toc-nav-text">1&#x3001;&#x4F7F;&#x7528; KeySet &#x904D;&#x5386;</span></a></li><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#2-使用-values-遍历"><span class="toc-nav-number">14.2.2.</span> <span class="toc-nav-text">2&#x3001;&#x4F7F;&#x7528; Values &#x904D;&#x5386;</span></a></li><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#3-使用-entry-遍历"><span class="toc-nav-number">14.2.3.</span> <span class="toc-nav-text">3&#x3001;&#x4F7F;&#x7528; Entry &#x904D;&#x5386;</span></a></li></ol></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#map的实现类"><span class="toc-nav-number">14.3.</span> <span class="toc-nav-text">Map&#x7684;&#x5B9E;&#x73B0;&#x7C7B;</span></a></li></ol></li><li class="toc-nav-item toc-nav-level-1"><a class="toc-nav-link" href="#hashmap"><span class="toc-nav-number">15.</span> <span class="toc-nav-text">HashMap</span></a><ol class="toc-nav-child"><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#hashmap的特点"><span class="toc-nav-number">15.1.</span> <span class="toc-nav-text">HashMap&#x7684;&#x7279;&#x70B9;&#xFF1A;</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#hashmap的成员变量"><span class="toc-nav-number">15.2.</span> <span class="toc-nav-text">HashMap&#x7684;&#x6210;&#x5458;&#x53D8;&#x91CF;</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#hashmap的初始容量和加载因子"><span class="toc-nav-number">15.3.</span> <span class="toc-nav-text">HashMap&#x7684;&#x521D;&#x59CB;&#x5BB9;&#x91CF;&#x548C;&#x52A0;&#x8F7D;&#x56E0;&#x5B50;</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#hashmap-中的链表节点"><span class="toc-nav-number">15.4.</span> <span class="toc-nav-text">HashMap &#x4E2D;&#x7684;&#x94FE;&#x8868;&#x8282;&#x70B9;</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#hashmap中的添加操作"><span class="toc-nav-number">15.5.</span> <span class="toc-nav-text">&#x25B2;HashMap&#x4E2D;&#x7684;&#x6DFB;&#x52A0;&#x64CD;&#x4F5C;</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#hashmap中的哈希函数hash"><span class="toc-nav-number">15.6.</span> <span class="toc-nav-text">&#x25B2;HashMap&#x4E2D;&#x7684;&#x54C8;&#x5E0C;&#x51FD;&#x6570;hash()</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#hashmap中的初始化扩容方法resize"><span class="toc-nav-number">15.7.</span> <span class="toc-nav-text">&#x25B2;HashMap&#x4E2D;&#x7684;&#x521D;&#x59CB;&#x5316;/&#x6269;&#x5BB9;&#x65B9;&#x6CD5;resize()</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#hashmap的获取方法get"><span class="toc-nav-number">15.8.</span> <span class="toc-nav-text">HashMap&#x7684;&#x83B7;&#x53D6;&#x65B9;&#x6CD5;get()</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#总结"><span class="toc-nav-number">15.9.</span> <span class="toc-nav-text">&#x603B;&#x7ED3;</span></a></li></ol></li><li class="toc-nav-item toc-nav-level-1"><a class="toc-nav-link" href="#hashmap在jdk18后新增的红黑树结构"><span class="toc-nav-number">16.</span> <span class="toc-nav-text">HashMap&#x5728;JDK1.8&#x540E;&#x65B0;&#x589E;&#x7684;&#x7EA2;&#x9ED1;&#x6811;&#x7ED3;&#x6784;</span></a><ol class="toc-nav-child"><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#传统hashmap的缺点"><span class="toc-nav-number">16.1.</span> <span class="toc-nav-text">&#x4F20;&#x7EDF;HashMap&#x7684;&#x7F3A;&#x70B9;</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#红黑树"><span class="toc-nav-number">16.2.</span> <span class="toc-nav-text">&#x7EA2;&#x9ED1;&#x6811;</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#hashmap中关于红黑树的三个关键参数"><span class="toc-nav-number">16.3.</span> <span class="toc-nav-text">HashMap&#x4E2D;&#x5173;&#x4E8E;&#x7EA2;&#x9ED1;&#x6811;&#x7684;&#x4E09;&#x4E2A;&#x5173;&#x952E;&#x53C2;&#x6570;</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#桶的树形化操作treeifybin"><span class="toc-nav-number">16.4.</span> <span class="toc-nav-text">&#x6876;&#x7684;&#x6811;&#x5F62;&#x5316;&#x64CD;&#x4F5C;treeifyBin()</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#红黑树中添加元素puttreeval"><span class="toc-nav-number">16.5.</span> <span class="toc-nav-text">&#x7EA2;&#x9ED1;&#x6811;&#x4E2D;&#x6DFB;&#x52A0;&#x5143;&#x7D20;putTreeVal()</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#红黑树中查找元素gettreenode"><span class="toc-nav-number">16.6.</span> <span class="toc-nav-text">&#x7EA2;&#x9ED1;&#x6811;&#x4E2D;&#x67E5;&#x627E;&#x5143;&#x7D20;getTreeNode()</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#树形结构修剪split"><span class="toc-nav-number">16.7.</span> <span class="toc-nav-text">&#x6811;&#x5F62;&#x7ED3;&#x6784;&#x4FEE;&#x526A;split()</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#总结"><span class="toc-nav-number">16.8.</span> <span class="toc-nav-text">&#x603B;&#x7ED3;</span></a></li></ol></li></ol>
        
        </div>
      </aside>
    

                
            <!-- Sidebar Container -->
            <div class="
                col-lg-8 col-lg-offset-2
                col-md-10 col-md-offset-1
                sidebar-container">

                <!-- Featured Tags -->
                
                <section>
                    <!-- no hr -->
                    <h5><a href="/tags/">标签</a></h5>
                    <div class="tags">
                       
                          <a class="tag" href="/tags/#jdk学习之路" title="jdk学习之路">jdk学习之路</a>
                        
                    </div>
                </section>
                

                <!-- Friends Blog -->
				<!--
                
                <hr>
                <h5>朋友们</h5>
                <ul class="list-inline">

                    
                        <li><a href="https://tyzhang.top/" target="_blank">ztygalaxy</a></li>
                    
                        <li><a href="http://www.yctang.club/" target="_blank">yctang</a></li>
                    
                        <li><a href="https://dolnw.github.io" target="_blank">JCWang</a></li>
                    
                </ul>
                
				-->
            </div>
        </div>
    </div>
</article>


<!-- async load function -->
<script>
    function async(u, c) {
      var d = document, t = 'script',
          o = d.createElement(t),
          s = d.getElementsByTagName(t)[0];
      o.src = u;
      if (c) { o.addEventListener('load', function (e) { c(null, e); }, false); }
      s.parentNode.insertBefore(o, s);
    }
</script>
<!-- anchor-js, Doc:http://bryanbraun.github.io/anchorjs/ -->
<script>
    async("https://cdn.bootcss.com/anchor-js/1.1.1/anchor.min.js",function(){
        anchors.options = {
          visible: 'hover',
          placement: 'left',
          icon: ''
        };
        anchors.add().remove('.intro-header h1').remove('.subheading').remove('.sidebar-container h5');
    })
</script>
<style>
    /* place left on bigger screen */
    @media all and (min-width: 800px) {
        .anchorjs-link{
            position: absolute;
            left: -0.75em;
            font-size: 1.1em;
            margin-top : -0.1em;
        }
    }
</style>


<!-- chrome Firefox 中文锚点定位失效-->
<script src="https://cdn.bootcss.com/jquery/3.3.1/jquery.js"></script>
<!-- smooth scroll behavior polyfill  -->
<script type="text/javascript" src="/js/smoothscroll.js"></script>
<script>
        $('#toc').on('click','a',function(a){
            // var isChrome = window.navigator.userAgent.indexOf("Chrome") !== -1;
            // console.log(window.navigator.userAgent,isChrome)
                // if(isChrome) {
                    // console.log(a.currentTarget.outerHTML);
                    // console.log($(a.currentTarget).attr("href"));
                    //跳转到指定锚点
                    // document.getElementById(a.target.innerText.toLowerCase()).scrollIntoView(true);
                    document.getElementById($(a.currentTarget).attr("href").replace("#","")).scrollIntoView({behavior: 'smooth' });
                // }
        })  
</script>


    <!-- Footer -->
    <!-- Footer -->
<footer>
    <div class="container">
        <div class="row">
            <div class="col-lg-8 col-lg-offset-2 col-md-10 col-md-offset-1">
                <ul class="list-inline text-center">
                
                
                
				
                

                

                
                    <li>
                        <a target="_blank"  href="https://github.com/songzblink">
                            <span class="fa-stack fa-lg">
                                <i class="fa fa-circle fa-stack-2x"></i>
                                <i class="fa fa-github fa-stack-1x fa-inverse"></i>
                            </span>
                        </a>
                    </li>
                

                

                </ul>
                <p class="copyright text-muted">
                    Copyright &copy; 宋正兵 2021 
                    <br>
                    Theme by <a href="http://www.huweihuang.com">Huwei Huang</a>
                    re-Ported by <a href="https://github.com/ztygalaxy">ztygalaxy</a>
					
                </p>
            </div>
        </div>
    </div>
</footer>

<!-- jQuery -->
<script src="/js/jquery.min.js"></script>

<!-- Bootstrap Core JavaScript -->
<script src="/js/bootstrap.min.js"></script>

<!-- Custom Theme JavaScript -->
<script src="/js/hux-blog.min.js"></script>


<!-- async load function -->
<script>
    function async(u, c) {
      var d = document, t = 'script',
          o = d.createElement(t),
          s = d.getElementsByTagName(t)[0];
      o.src = u;
      if (c) { o.addEventListener('load', function (e) { c(null, e); }, false); }
      s.parentNode.insertBefore(o, s);
    }
</script>

<!-- 
     Because of the native support for backtick-style fenced code blocks 
     right within the Markdown is landed in Github Pages, 
     From V1.6, There is no need for Highlight.js, 
     so Huxblog drops it officially.

     - https://github.com/blog/2100-github-pages-now-faster-and-simpler-with-jekyll-3-0  
     - https://help.github.com/articles/creating-and-highlighting-code-blocks/    
-->
<!--
    <script>
        async("http://cdn.bootcss.com/highlight.js/8.6/highlight.min.js", function(){
            hljs.initHighlightingOnLoad();
        })
    </script>
    <link href="http://cdn.bootcss.com/highlight.js/8.6/styles/github.min.css" rel="stylesheet">
-->


<!-- jquery.tagcloud.js -->
<script>
    // only load tagcloud.js in tag.html
    if($('#tag_cloud').length !== 0){
        async("zbsong.top/js/jquery.tagcloud.js",function(){
            $.fn.tagcloud.defaults = {
                //size: {start: 1, end: 1, unit: 'em'},
                color: {start: '#bbbbee', end: '#0085a1'},
            };
            $('#tag_cloud a').tagcloud();
        })
    }
</script>

<!--fastClick.js -->
<script>
    async("https://cdn.bootcss.com/fastclick/1.0.6/fastclick.min.js", function(){
        var $nav = document.querySelector("nav");
        if($nav) FastClick.attach($nav);
    })
</script>


<!-- Google Analytics -->




<!-- Baidu Tongji -->






	<a id="rocket" href="#top" class=""></a>
	<script type="text/javascript" src="/js/totop.js?v=1.0.0" async=""></script>
    <script type="text/javascript" src="/js/toc.js?v=1.0.0" async=""></script>
<!-- Image to hack wechat -->
<img src="zbsong.top/img/icon_wechat.png" width="0" height="0" />
<!-- Migrate from head to bottom, no longer block render and still work -->

<script type="text/x-mathjax-config">
    MathJax.Hub.Config({
        tex2jax: {
            inlineMath: [ ["$","$"], ["\\(","\\)"] ],
            skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code'],
            processEscapes: true
        }
    });
    MathJax.Hub.Queue(function() {
        var all = MathJax.Hub.getAllJax();
        for (var i = 0; i < all.length; ++i)
            all[i].SourceElement().parentNode.className += ' has-jax';
    });
</script>
<!--
<script src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
-->
<script src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-MML-AM_CHTML"></script>
</body>

</html>
